Unary comparison of a threshold with an answer is polynomial-time
ProvedTetrisHard.Rows.unary_lt_decidercomplexity-theory
There is a polynomial-time computable map on words over the tagged alphabet such that for all natural numbers ,
where is the self-delimiting unary code, the left word is tagged with the first summand and the right word with the second.
This is the final comparison step of the gap decision procedure in Theorem 6.5.
Preamble
import Definitions.Def_TetrisHard_Rows_ThreePartition
Formal statement
namespace TetrisHard.Rows
theorem unary_lt_decider :
∃ g : List (Option (Bool ⊕ Bool)) → List Bool, CookPvsNP.PolyTimeComputable g ∧
∀ a v : ℕ, g ((unaryCode [a]).map (some ∘ Sum.inl) ++
none :: (unaryCode [v]).map (some ∘ Sum.inr)) = [decide (a < v)] := 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