pith. machine review for the scientific record. sign in
theorem proved term proof

polynomial_time_3sat_algorithm

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

 185theorem polynomial_time_3sat_algorithm (n : Nat)
 186    (h : polynomial_time_3sat_algorithm_hypothesis n) :
 187    ProgramTarget n →
 188    ∃ (alg : CNF n → Option (Assignment n)),
 189      (∀ φ, Satisfiable φ → ∃ x, alg φ = some x ∧ evalCNF x φ = true) ∧
 190      (∀ φ, ¬Satisfiable φ → alg φ = none) :=

proof body

Term-mode proof.

 191  h
 192
 193/-- Backpropagation succeeds when there is a unique solution under XOR constraints.
 194This is a semantic existence result that does not rely on a specific step system. -/

depends on (12)

Lean names referenced from this declaration's body.