Polynomial-time many-one reduction from 3-SAT to unary 3-Partition
ProvedTetrisHard.Rows.ksat3_polyReducible_threePartitioncomplexity-theorytetris
Binary-encoded 3-SAT is polynomial-time many-one reducible to unary-encoded 3-Partition:
Following Garey and Johnson's strong NP-completeness proof (3-SAT 3-Dimensional Matching 4-Partition 3-Partition), a 3-CNF formula with variables and clauses is mapped to a valid 3-Partition instance whose part count and target are bounded by fixed polynomials in and . Because all numerical entries are polynomially bounded in the formula length, emitting the unary encoding takes polynomial time.
Preamble
import Definitions.Def_TetrisHard_Rows_ThreePartition import Definitions.Def_KSat_Languages
Formal statement
namespace TetrisHard.Rows
theorem ksat3_polyReducible_threePartition :
CookPvsNP.PolyReducible {w : List Bool | KSat.KSAT 3 w} threePartitionLanguage := 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)