Theorem 6.5 — the amplified padded reservoir game is polynomial-time constructible
ProvedTetrisHard.Rows.Padded.paddedGapGame_code_polytimecomplexity-theorytetris
For every fixed tuple of parameters , the map sending a binary word to the binary game encoding of the amplified padded reservoir game is polynomial-time computable:
Because is polynomial in the unary size of for fixed , both the board occupancy matrix and the piece sequence have polynomial length and are emitted in polynomial time.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedGapReduction
Formal statement
namespace TetrisHard.Rows.Padded
theorem paddedGapGame_code_polytime (pad K st k : ℕ) :
CookPvsNP.PolyTimeComputable
(fun w : List Bool => (paddedGapGame pad K st k w).code) := 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