The Cook-Levin Theorem: NP-Completeness of Boolean Satisfiability in Lean 4Research Paper
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.
A collection of NP-Complete problems as well as helpers.
6 completed missions
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 that CLIQUE is NP-complete by reducing the existing 3-SAT language, KSat.KSAT 3, to it. An instance consists of a finite simple undirected graph and an input threshold; it asks whether the graph contains a clique of at least that size.
(https://prove2.me/theorems/d82e8682-c490-4742-a5e5-dd3a0b870b90). The construction specializes Karp’s SAT-to-CLIQUE…
Prove that subset sum is NP-complete by reducing the existing 3-SAT language, to it. Given a list of positive integers and a nonnegative target, decide whether some selection of entries sums exactly to the target. Integers are encoded in binary.
Prove that -SAT is NP-complete for every fixed , with at most literal occurrences per clause.
We establish the polynomial simulation needed for WordRAM-based NP proofs. It reuses the same machines and Cook–Levin definitions, with uniform programs, logarithmic word widths, and standard bit input/output.
We formalize the equivalence between Turing machines and the WordRAM model of computation. Turing machines are the standard model for studying computability, but algorithms are rarely described in terms of tape operations. WordRAM is much closer to assembly, with memory accesses, arithmetic instructions, branches, and loops. The goal is to connect this…
| Rank | Contributor | Accepted solutions | Submitted problems |
|---|---|---|---|
| 1 | Eyal1990 | 50 | 64 |
| 2 | Robertboy18 | 44 | 34 |
| 3 | Rizwan G Mir | 32 | 96 |
| 3 | wurtle | 32 | 66 |
| 5 | cm_beta | 24 | 0 |
| 5 | junyihjy | 24 | 26 |
| 7 | fizzyinc3 | 20 | 0 |
| 8 | Mazecto | 16 | 31 |
| 9 | chstdu | 5 | 2 |
| 10 | carlok | 1 | 0 |