Theorem 1, proof (p. 8) — condition (vi) is checkable in NP
OpenKarpPapadimitriou.Facial.basicDualLang_mem_NPLet be a combinatorial optimization problem and let be a small facial description of such that (the language of codes of its triples is in NP).
Let be the language of all strings over the alphabet with the following property: whenever with , , , and , condition (vi) of the proof of Theorem 1 holds, namely there are an integer matrix with and an integer vector such that
and the system has a (necessarily unique) nonnegative rational solution with
(Strings that encode no such triple, and triples with , belong to vacuously.) Then
This is the complexity half of the proof of Theorem 1 of Karp and Papadimitriou (the assertion that condition (vi) can be checked in NP). Combined with the equivalences (i)(vi) of that proof, it yields co-NP.
Formalization Note P and NP are Cook's classes over the alphabet with integers in binary. Uniqueness of is expressed by . For strings that are not codes, or codes with , membership is automatic; a proof must therefore also certify, in NP, that a string is not a well-formed code with , and (using the facial description) that .
import Mathlib import Definitions.Def_KarpPapadimitriou_Facial_FacialDescription
namespace KarpPapadimitriou.Facial
open CookPvsNP ProjSchedTW.Complexity
theorem basicDualLang_mem_NP (C : COP) (F : Triples C) (hF : IsFacialDescription C F)
(hs : IsSmall C F) (hNP : tripleLang C F ∈ NP BSym) :
{w : List BSym | ∀ z ∈ C.L, ∀ (c : Fin (C.n z) → ℤ) (k : ℤ), w = encTriple z c k →
(C.S z).Nonempty →
∃ (fm : Matrix (Fin (C.n z)) (Fin (C.n z)) ℤ) (g : Fin (C.n z) → ℤ),
(∀ i, (⟨z, (fm i, g i)⟩ : Σ z : List Bool, (Fin (C.n z) → ℤ) × ℤ) ∈ F) ∧
fm.det ≠ 0 ∧
∃ y : Fin (C.n z) → ℚ,
Matrix.vecMul y (fm.map (fun a : ℤ => (a : ℚ))) = (fun j => (c j : ℚ)) ∧
0 ≤ y ∧ y ⬝ᵥ (fun i => (g i : ℚ)) < (k : ℚ)} ∈ NP BSym := by sorry
end KarpPapadimitriou.Facial