p. 367, proof of THEOREM 2, part (ii) — a dominating edge-set with |F| = 3n gives a satisfying assignment τ
ProvedEdgeDomSets.NPC.part_iiLet be a SAT-3-restricted formula with variables and an edge dominating set of with . Then contains neither nor , so it contains either or both and . Let set in the first case and in the second. Then
With part (i), is satisfiable if and only if has an edge dominating set of size .
Formalization Note Clause and position indices are 0-based (Fin). The vertices of are indexed by literal occurrences: the occurrence has a literal vertex lit o (the paper's , or ), a pendant pend o (the primed copy) and a variable-side vertex varNode o ( or for the two positive occurrences of , for the negated one); dNode j, dNode' j are , . The assignment is assignOfEdges φ F: iff contains the edge at the negated occurrence of , and otherwise.
Differences from the source:
- encoding: vertices a_i, b_i, c_i, (a_i, j1), (b_i, j2), (c_i, j3), their primed copies, d_j, d'_j, with 1-based indices → one literal vertex, one pendant vertex and one variable-side vertex per literal occurrence (clause index, position), plus d_j, d'_j, all 0-based (
Fin); reason: under SAT-3-restricted the three occurrences of x_i are exactly x_i ∈ C_j1, x_i ∈ C_j2, x̄_i ∈ C_j3, so the vertices and edges are the printed ones - encoding: τ: x_i = 1 if F has ((c_i, j3), c_i), x_i = 0 if F has both ((a_i, j1), a_i) and ((b_i, j2), b_i) → x_v = 1 iff F has ((c_i, j3), c_i), x_v = 0 otherwise; reason: under the hypotheses exactly one of the two cases holds, so the assignments agree on every variable of φ
- generalization: a set of clauses with at most three literals per clause, every variable occurring two times and its negation once → IsSat3Restricted φ on a list of literal lists: occurrences counted with multiplicity, so a clause may repeat a literal or hold x and x̄, clauses may repeat, and empty clauses are allowed; reason: every instance of the printed problem satisfies IsSat3Restricted, so the statement specializes to the source's claim on each of them; the construction and the argument are unchanged on the extra formulas (paper.md reading 4)
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
namespace EdgeDomSets.NPC
theorem part_ii (φ : CookLevin.Formula) (hφ : IsSat3Restricted φ)
(F : Finset (Sym2 (GV φ))) (hF : IsEdgeDominating (G φ) F)
(hcard : F.card = 3 * numVars φ) :
CookLevin.Satisfies (assignOfEdges φ F) φ := by sorry
end EdgeDomSets.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.