`rsatSeparation`

proved

show as: view math explainer →

module: IndisputableMonolith.Complexity.RSatEncoding
domain: Complexity
line: 261 · github
papers citing: none yet

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Complexity.RSatEncoding on GitHub at line 261.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

depends on

formal source

 258  unsat_obstruction : ∀ n : ℕ, ∀ f : CNFFormula n, f.isUNSAT →
 259    ∀ a : Assignment n, satJCost f a ≥ 1
 260
 261theorem rsatSeparation : RSATSeparation where
 262  sat_polytime := fun n f h =>
 263    let ⟨steps, a, hle, ha⟩ := sat_recognition_time_bound f h
 264    ⟨steps, hle, a, ha⟩
 265  local_certifier_fails := fun n M hcard =>
 266    let ⟨b, R, g_eq⟩ := BalancedParityHidden.adversarial_failure M (fun _ => true)
 267    ⟨b, R, fun _ => true, g_eq⟩
 268  unsat_obstruction := fun n f h => unsat_cost_lower_bound f h
 269
 270end RSatEncoding
 271end Complexity
 272end IndisputableMonolith

papers checked against this theorem

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