CNF formulas with exactly one satisfying assignment
DefinitionICSCompute_Supplement_UniquelySatcomplexity-theoryindefinite-causal-orderp2o-gran-per-chapterp2o-plan-paperp2o-v1process-matricesquantum-information
A CNF formula has exactly one satisfying assignment if some truth assignment satisfies and any two satisfying assignments agree on every variable occurring in .
This is the condition under which the Valiant–Vazirani reduction is useful and under which the generation queries of the SAT algorithm of Theorem 5.2 are valid PMGs with unitary generated channels.
Formalization Note Formulas and assignments are those of the published PvsNP layer, where an assignment gives a value to every variable index in . The value of depends only on the variables occurring in it, so uniqueness is taken relative to those variables; uniqueness among all assignments would fail for every satisfiable formula.
Definition code
import Mathlib
import Definitions.Def_PvsNP
namespace ICSCompute.Supplement
/-- The indices of the variables occurring in a CNF formula. -/
def cnfVars (φ : PvsNP.CNF) : Set ℕ :=
{i | ∃ c ∈ φ, ∃ s : Bool, (s, i) ∈ c}
/-- **A CNF formula with exactly one satisfying assignment** (Shmueli, *What Can Be Computed with
Indefinite Causal Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606,
Theorem 5.2, p.29 (PDF p.31): "the formula used in a query has exactly one satisfying
assignment"; Definition 3.7 and Theorem 3.1, pp.15–16).
`φ` has exactly one satisfying assignment to its variables: some assignment satisfies `φ`, and
any two satisfying assignments agree on every variable occurring in `φ`.
**Formalization Note** The published `PvsNP` assignments are functions `τ : ℕ → Bool` on all
variables, and the value of `φ` depends only on the variables occurring in it, so "exactly one"
is relative to those variables; `∃! τ : ℕ → Bool` would be false for every satisfiable formula. -/
def UniquelySat (φ : PvsNP.CNF) : Prop :=
∃ τ : ℕ → Bool, PvsNP.evalCNF τ φ = true ∧
∀ τ' : ℕ → Bool, PvsNP.evalCNF τ' φ = true → ∀ i ∈ cnfVars φ, τ' i = τ i
end ICSCompute.Supplement
Source
Shmueli, What Can Be Computed with Indefinite Causal Structure?, arXiv:2610.40573 (version of 2026-11-03, sha256 d3e36399…b606), Theorem 5.2, p.29 (PDF p.31); Definition 3.7 and Theorem 3.1, pp.15–16 (PDF pp.17–18)