`CNFWithXOR`

definition

show as: view math explainer →

module: IndisputableMonolith.Complexity.SAT.XOR
domain: Complexity
line: 95 · github
papers citing: none yet

open explainer

Read the cached plain-language explainer.

open lean source

IndisputableMonolith.Complexity.SAT.XOR on GitHub at line 95.

browse module

All declarations in this module, on Recognition.

explainer page

A cached Ask Recognition explainer exists for this declaration.

open explainer

depends on

used by

formal source

  92    _ = Bool.xor p (parityOf a vs) := by rw [hp]
  93
  94/-- CNF "under XOR constraints": we don't rewrite into CNF; we pair them semantically. -/
  95structure CNFWithXOR (n : Nat) where
  96  φ : CNF n
  97  H : XORSystem n
  98
  99/-- Satisfiable under XOR constraints. -/
 100def SatisfiableXOR {n} (ψ : CNFWithXOR n) : Prop :=
 101  ∃ a : Assignment n, evalCNF a ψ.φ = true ∧ satisfiesSystem a ψ.H
 102
 103/-- Unique solution under XOR constraints. -/
 104def UniqueSolutionXOR {n} (ψ : CNFWithXOR n) : Prop :=
 105  ∃! a : Assignment n, evalCNF a ψ.φ = true ∧ satisfiesSystem a ψ.H
 106
 107end SAT
 108end Complexity
 109end IndisputableMonolith

papers checked against this theorem

No papers in the current corpus map onto this theorem yet.