Theorem 6.5 — the padded no-case threshold is polynomial-time computable
ProvedTetrisHard.Rows.Padded.paddedNoBound_code_polytimecomplexity-theorytetris
For every fixed padding parameter , chimney parameter , and staging allowance , the map sending a binary word to the unary encoding of the no-case cleared-row bound is computable in polynomial time:
This supplies the polynomial-time threshold used by the gap decision procedure in Theorem 6.5.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedGapReduction
Formal statement
namespace TetrisHard.Rows.Padded
theorem paddedNoBound_code_polytime (pad K st : ℕ) :
CookPvsNP.PolyTimeComputable
(fun w : List Bool => unaryCode [paddedNoBound (normInstance w) 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