Theorem 6.5 — the amplified reservoir game is polynomial-time constructible
ProvedTetrisHard.Rows.gapGame_code_polytimecomplexity-theorytetris
For every fixed staging allowance and exponent parameter , the map sending a binary word to the code of the amplified reservoir game is polynomial-time computable (Cook's one-tape Turing machines).
Here the word is decoded as a unary 3-Partition instance, normalized by scaling with (degenerate or invalid words are sent to fixed yes/no instances), and the game of Figure 9(b) is built with reservoir height . The game code lists the dimensions in unary, the full occupancy matrix, and the piece sequence.
This is the polynomiality remark in the proof of Theorem 6.5 ('r, and thus our game, is still polynomial in the size of the 3-Partition instance'), resting on Theorem 3.2 and the strong NP-hardness of 3-Partition (unary entries).
Preamble
import Definitions.Def_TetrisHard_Rows_GapReduction
Formal statement
namespace TetrisHard.Rows
theorem gapGame_code_polytime (staging k : ℕ) :
CookPvsNP.PolyTimeComputable (fun w : List Bool => (gapGame staging k w).code) := by sorry
end TetrisHard.Rows
Source
Demaine, Hohenberger and Liben-Nowell, Tetris is Hard, Even to Approximate, arXiv:cs/0210020v1, Theorem 3.2 (p. 8) and proof of Theorem 6.5 (p. 21), https://arxiv.org/abs/cs/0210020v1