Theorem 6.5, no case — cumulative cleared rows bounded independently of r in the padded reservoir game
ProvedTetrisHard.Rows.Padded.paddedReservoir_soundnesscomplexity-theorytetris
Let be an admissible reasonable rotation model, let be a valid normalized no-instance of 3-Partition with , and let , , , and . Every attainable cleared-row count of satisfies
a polynomial bound independent of .
Because the buffer shaft and filled columns preserve the BucketFrame local neighborhood invariant for buckets and leave at most one piece of area slack above the second lock, no-instances cannot clear all chimney rows before the square sequence begins; the surviving one-wide chimney blocks squares from entering the reservoir, and odd board width bounds square row clears above the second lock via row-occupancy parity.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedGapReduction
Formal statement
namespace TetrisHard.Rows.Padded
theorem paddedReservoir_soundness
(R : Rotation) (hR : R.Admissible) (hReason : Reasonable R)
(P : ThreePartition) (hP : P.Valid) (hN : P.Normalized) (hs : 0 < P.s)
(hno : ¬ P.HasSolution)
(pad K st r : ℕ)
(hpad : max R.radius 2 + 2 ≤ pad)
(hK : maxJump R + 2 ≤ K)
(hst : 5 * max R.radius 2 + 12 ≤ st) :
∀ v, Attainable R (paddedReservoirGame P pad K st r) v →
v ≤ paddedNoBound P pad K st := by sorry
end TetrisHard.Rows.Padded
Source
Demaine, Hohenberger and Liben-Nowell, Tetris is Hard, Even to Approximate, arXiv:cs/0210020v1, Section 3 (p. 7), Section 5.3 (pp. 12-14), Section 6.2 and Figure 9(b) (pp. 19-21), Theorem 6.5 (p. 21), https://arxiv.org/abs/cs/0210020v1