Amplified reservoir game, normalized source instance and no-case bound for Theorem 6.5
DefinitionTetrisHard_Rows_GapReductionAuxiliary objects for the inapproximability of cleared rows (Theorem 6.5).
- Scaling. For a 3-Partition instance , multiplies the target and every entry by . This is the normalization of Section 3: validity and the answer are preserved, the target becomes even, and every subset sum different from the target misses it by at least .
- Fixed instances. is a valid yes-instance; is a valid no-instance (every triple sums to or ).
- Decoding a word. For a binary word , is the valid instance with at least one part coded by , if there is one; the fixed yes-instance if codes a valid instance with (such instances are always yes-instances); and the fixed no-instance otherwise. .
- No-case bound. With the height of the base board (including its staging rows) and the length of the base piece sequence,
This number does not depend on the reservoir height : is the number of rows at or above the second lock in Figure 9(b), and is the area of all pieces up to and including the extra RG. 5. Reservoir height. With (so the amplified sequence has at most pieces for ) and a fixed exponent parameter ,
an even number polynomial in the unary size of for fixed . 6. Amplified game. is the reservoir game of Figure 9(b) for with staging and reservoir height .
These objects make the choice " rows in the reservoir" of the proof of Theorem 6.5 explicit and polynomial.
Formalization Note The paper's no-case bound "at most rows" is replaced by the conservative cumulative bound above, which accounts separately for rows cleared before and during the final square sequence; the final exponent is unaffected.
import Definitions.Def_TetrisHard_Rows_Reservoir
namespace TetrisHard.Rows
/-- Multiply every entry and the target by `6s`. This preserves validity and the answer,
and makes the target even with all subset-sum gaps multiples of `6s` (Section 3). -/
def ThreePartition.scale (P : ThreePartition) : ThreePartition where
s := P.s
target := 6 * P.s * P.target
entry := fun i => 6 * P.s * P.entry i
/-- A fixed valid "yes" instance with one part: `1+1+1 = 3`. -/
def yesInstance : ThreePartition := ⟨1, 3, fun _ => 1⟩
/-- A fixed valid "no" instance with two parts: entries `4,4,4,4,4,6`, target `13`;
every triple sums to `12` or `14`. -/
def noInstance : ThreePartition := ⟨2, 13, ![4, 4, 4, 4, 4, 6]⟩
/-- Decode a binary word as a source instance. Codes of valid instances with at least one
part decode to that instance; codes of valid empty instances (always "yes") decode to the
fixed yes instance; every other word decodes to the fixed no instance. -/
noncomputable def rawInstance (w : List Bool) : ThreePartition := by
classical
exact if h : ∃ P : ThreePartition, P.Valid ∧ 0 < P.s ∧ w = P.code then Classical.choose h
else if ∃ P : ThreePartition, P.Valid ∧ w = P.code then yesInstance else noInstance
/-- The normalized source instance attached to a binary word. -/
noncomputable def normInstance (w : List Bool) : ThreePartition := (rawInstance w).scale
/-- Polynomial bound on the cumulative number of rows cleared in a "no" instance:
twice the number of rows at or above the second lock, plus the area of all pieces
before the appended squares. It does not depend on the reservoir height. -/
def noBound (P : ThreePartition) (staging : ℕ) : ℕ :=
2 * ((baseBoard P staging).height + 2) + 4 * ((basePieces P).length + 1)
/-- A factor with `|pieces| ≤ pieceFactor P * r` for every positive reservoir height `r`. -/
def pieceFactor (P : ThreePartition) : ℕ := (basePieces P).length + 6 * P.s + 7
/-- The explicit (even) reservoir height for the exponent parameter `k`. -/
def gapRows (P : ThreePartition) (staging k : ℕ) : ℕ :=
2 * (noBound P staging * pieceFactor P + 1) ^ k
/-- The amplified Tetris game attached to a binary word. -/
noncomputable def gapGame (staging k : ℕ) (w : List Bool) : Game :=
reservoirGame (normInstance w) staging (gapRows (normInstance w) staging k)
end TetrisHard.Rows