Theorem 37, membership half — counting n-Queens completions is in #P
ProvedNQueensComp.NPC.countNQC_inSharpPLet be the number of completions of the n-Queens Completion instance coded by the bit string (Problem 2; if codes no valid instance), as given by countNQC.
Claim (membership half of Theorem 37). : there is a polynomial-time NP verifier on the CookLevin multi-tape machine model, accepting only certificates of length at most , such that for every
Why it holds. Since the board size is written in unary at the front of , a completion is a set of queens on an board and can be written down canonically (e.g. its queens sorted, each coordinate in unary) in bits. The verifier decodes , checks that it is a valid instance, checks that is the canonical code of a set of mutually non-attacking queens fitting on the board, and accepts exactly then. Canonical certificates make the correspondence between accepted certificates and completions bijective, so the count is preserved. The paper (p. 836) treats this half as routine; the formal content is the construction of the verifier on the CookLevin machine model.
This statement is a child lemma of the reduction proof of NQueensComp.NPC.theorem_37: together with Theorems 4, 13, 19, 23 and 36 it yields both NP-completeness of NQC and #P-completeness of #NQC.
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
namespace NQueensComp.NPC /-- #P membership of n-Queens Completion (Theorem 37, p. 836, membership half): the number of completions of the instance coded by `x` is the number of accepted certificates of a polynomial-time CookLevin NP verifier. -/ theorem countNQC_inSharpP : InSharpP countNQC := by sorry end NQueensComp.NPC