Unary 3-Partition lies in NP
ProvedTetrisHard.Rows.threePartition_mem_NPcomplexity-theorytetris
Let denote the language of self-delimiting unary encodings of valid 3-Partition instances (satisfying and for all ) that admit a partition into triples each summing to . Then
A nondeterministic certificate specifies the part index assigned to each in unary; its length is bounded quadratically in the unary input length, and validity plus the part-sum equations are verifiable in polynomial time on a one-tape Turing machine.
Preamble
import Definitions.Def_TetrisHard_Rows_ThreePartition
Formal statement
namespace TetrisHard.Rows
theorem threePartition_mem_NP :
threePartitionLanguage ∈ CookPvsNP.NP Bool := by sorry
end TetrisHard.Rows
Source
Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Theorem 4.4 (pp. 96-105); Demaine, Hohenberger and Liben-Nowell, Tetris is Hard, Even to Approximate, arXiv:cs/0210020v1, Section 3 (p. 7)