Theorem 23, code level — a polynomial-time parsimonious map on bit codes
OpenNQueensComp.NPC.theorem_23_codesClaim (code-level half of Theorem 23, p. 831). There is a map on bit strings, computable in polynomial time on the CookLevin multi-tape machine model, such that
- for every valid instance of Problem 5 and every code of , is a code of (the instance of Problem 4 given by Definition 20 (corrected: ends at ; the empty family is sent to )); and
- preserves the number of solutions of every input string:
where a string that codes no valid instance has count .
Item 2 is what makes a parsimonious reduction. On codes of valid instances it follows from item 1 and the instance-level half theorem_23_instances; on all other strings must output a string of count . The substantive work is implementing the decoding, the construction and the encoding as a polynomial-time machine, which the paper treats as routine (instances are coded with unary numbers, so all constructions are polynomial in the code length).
This is one of the two halves of NQueensComp.NPC.theorem_23.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).
import Mathlib import Definitions.Def_NQueensComp_NPC_SharpP import Definitions.Def_NQueensComp_NPC_Codes import Definitions.Def_NQueensComp_NPC_Reductions
namespace NQueensComp.NPC
/-- Theorem 23, code-level half. -/
theorem theorem_23_codes :
∃ R : List Bool → List Bool, CookLevin.IsPolyTimeComputable R ∧
(∀ (Ms : Inst5) (Ls : Code5), Inst5Valid Ms → Rep5 Ls Ms →
∃ L₄ : Code4, L₄.Rep (def20 Ms) ∧ R (enc5 Ls) = L₄.enc) ∧
∀ x : List Bool, count5 x = count4 (R x) := by sorry
end NQueensComp.NPC