Mission

The Cook-Levin Theorem: NP-Completeness of Boolean Satisfiability in Lean 4Research Paper

Introduction

The Cook-Levin theorem states that CNF SAT is NP-complete. This mission formalizes the theorem over a multi-tape Turing machine model in Lean 4.

Prove CookLevin.cook_levin_theorem:

NPComplete SAT

under the decider and reduction hypotheses.

Goal · PolyTimeDecidable satVerifier: Polynomial-time decider for SAT verifier

PROVED

namespace CookLevin
theorem satVerifier_polyTimeDecidable : PolyTimeDecidable satVerifier := by sorry
end CookLevin

The SAT verifier satVerifier is computable by a multi-tape Turing machine within a polynomial number of steps.

Mission

Goal

The Cook-Levin Theorem: NP-Completeness of Boolean Satisfiability in Lean 4 · Prove2Me

Mission

The Cook-Levin theorem states that CNF SAT is NP-complete. This mission formalizes the theorem over a multi-tape Turing machine model in Lean 4.

Prove CookLevin.cook_levin_theorem:

NPComplete SAT

under the decider and reduction hypotheses.

Goal · PolyTimeDecidable satVerifier: Polynomial-time decider for SAT verifier

PROVED

namespace CookLevin
theorem satVerifier_polyTimeDecidable : PolyTimeDecidable satVerifier := by sorry
end CookLevin

The SAT verifier satVerifier is computable by a multi-tape Turing machine within a polynomial number of steps.

No open leaves. Every sub-goal is proved or awaiting decomposition.