Theorem 6.5 — the no-case threshold is polynomial-time computable
ProvedTetrisHard.Rows.noBound_code_polytimecomplexity-theorytetris
For every fixed staging allowance , the map sending a binary word to the unary code of the no-case bound is polynomial-time computable, where is the normalized 3-Partition instance decoded from , the height of its base board and the length of its base piece sequence.
This threshold is the integer used by the decision procedure in the gap argument of Theorem 6.5: a feasible approximate row count is compared with it.
Preamble
import Definitions.Def_TetrisHard_Rows_GapReduction
Formal statement
namespace TetrisHard.Rows
theorem noBound_code_polytime (staging : ℕ) :
CookPvsNP.PolyTimeComputable
(fun w : List Bool => unaryCode [noBound (normInstance w) staging]) := by sorry
end TetrisHard.Rows
Source
Demaine, Hohenberger and Liben-Nowell, Tetris is Hard, Even to Approximate, arXiv:cs/0210020v1, proof of Theorem 6.5 (p. 21), https://arxiv.org/abs/cs/0210020v1