Theorem 19, code level — a polynomial-time parsimonious map on bit codes
OpenNQueensComp.NPC.theorem_19_codesClaim (code-level half of Theorem 19, p. 827). 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 4 (Excluded Diagonals) and every code of , is a code of (the instance of Problem 3 given by Definition 16); 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_19_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_19.
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 19, code-level half. -/
theorem theorem_19_codes :
∃ R : List Bool → List Bool, CookLevin.IsPolyTimeComputable R ∧
(∀ (M : Inst4) (L : Code4), M.Valid → L.Rep M →
∃ L₃ : Code3, L₃.Rep (def16 M) ∧ R L.enc = L₃.enc) ∧
∀ x : List Bool, count4 x = count3 (R x) := by sorry
end NQueensComp.NPC