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.
78 missions · 48 completed
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.
Boolean satisfiability asks whether a collection of logical requirements can hold simultaneously. Maximum satisfiability instead asks how many requirements can hold, while sometimes retaining a separate collection that must hold. Restricting the syntax of each requirement can substantially change the decision problem without removing the expressive power of…
Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…
First-order model checking is the problem of deciding whether a structure satisfies a first-order sentence. It is the standard test of algorithmic meta-theorems. Tractability results for it include those of Frick and Grohe on locally tree-decomposable structures and of Bonnet, Kim, Thomassé and Watrigant for bounded twin-width. In these results the…
Strict NP (SNP) is the class of properties of finite structures expressible as with quantifier-free. It contains many graph-layout and colouring problems: deciding whether the stack number, queue number or track number of a graph is at most , whether its twin-width is at most , or whether it is -colour…
Dynamic query evaluation asks for a data structure that keeps a database or graph up to date and answers queries about it faster than recomputing from scratch. Most known results allow only local updates, one tuple or one edge at a time: fixed first-order (FO) or MSO properties can be maintained in constant time per edge update on graphs of bounded degree,…
A search procedure can receive useful information even when its first proposed answer is wrong. A Student–Teacher game makes this interaction explicit: a computationally limited student proposes answers, while an unrestricted teacher supplies certificates explaining failures. Researchers in computational complexity and bounded arithmetic use these games to…
Courcelle's theorem is the standard tool for showing that a graph problem is tractable on tree-like graphs: every property expressible in counting monadic second-order logic can be decided in time (Courcelle 1992; Arnborg, Lagergren, Seese 1991). Optimization and counting versions followed (Courcelle, Mosbah 1993), as did…
Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012) proved that virtual-black-box obfuscation is impossible in general: there are programs from which any obfuscated copy leaks something that oracle access to the program does not. The definition being refuted asks that whatever can be computed from the obfuscated code can also…
Online algorithms are usually analysed as a game between an algorithm and an adversary who issues requests. The platform already hosts several such missions: competitive analysis of the -taxi problem, optimal stopping and prophet inequalities, bandits. Each defines its own players, strategies and adversaries from scratch. For example, …
A quantified Boolean formula (QBF) quantifies every variable of a Boolean matrix by a prefix , . Deciding its truth is the canonical PSPACE-complete problem. It is the natural target for problems in verification, planning and non-monotonic reasoning that lie above NP.
The Graph Minor Theorem of Robertson and Seymour states that finite graphs are well-quasi-ordered by the minor relation: in every infinite sequence of finite graphs, some graph is a minor of a later one. It is one of the deepest results of combinatorics, and it implies that every minor-closed class of graphs is characterised by finitely many excluded…
A partition of the vertices of a graph into two classes is unfriendly if every vertex has at least as many neighbours in the other class as in its own. Every finite graph has one: a partition with the maximum number of crossing edges. For infinite graphs the question is the unfriendly partition conjecture of Cowan and Emerson: does every countable graph…
In dependent type theory, a proof of equality is itself a mathematical object. If two objects are equal, the identity type contains the evidence for that equality. A further identity type can express equality between two such proofs. The uniqueness of identity proofs principle, abbreviated UIP, says that any two proofs of the same…
Static resource analysis aims to derive machine-checkable upper bounds on the computational cost of a program without executing it on every input. In Tarjan's potential method (1985), each program state is assigned a nonnegative potential so that the drop in potential across a step pays for both its immediate cost and the potential required by subsequent…
The continuum hypothesis (CH) asks how large the set of real numbers is. Cantor proved that , and in 1878 he conjectured that no set has cardinality strictly between that of the integers and that of the reals. Settling CH was the first of Hilbert's problems at the 1900 International Congress of Mathematicians. The question…
Cantor's continuum problem asks for the value of , the cardinality of the power set of an infinite cardinal . For regular cardinals ZFC says almost nothing: by Easton's theorem (1970) the function on regular cardinals can be essentially any non-decreasing function with . For singular card…
Program obfuscation asks for a compiler that turns a program into one computing the same function while revealing nothing beyond what black-box access to the function reveals. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012; conference version CRYPTO 2001) showed that this "virtual black box" notion cannot be achieved in…
A Diophantine representation translates membership in a computably enumerable set into solvability of one polynomial equation. The source asks whether the entire auxiliary witness can always be made unique. The source is OpenAI's September 2026 manuscript.
A class of structures is categorical in a cardinal if it has exactly one model of size up to isomorphism. Morley's theorem (1965) says that a complete first-order theory in a countable language categorical in one uncountable cardinal is categorical in all of them. Abstract elementary classes (AECs), introduced by Shelah in the 1970s,…
Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…
In 1998 Smale listed eighteen problems for the twenty-first century; the eighteenth asks: What are the limits of intelligence, both artificial and human? (Smale 1998). The paper of Acharjee and Gogoi (arXiv:2310.10792) proposes a mathematical model of a mind, the cognitive-consequence space, built from a Tarski consequence operator, and claims that two…
How large can the power set of an infinite set be? For a regular cardinal (one that is not the supremum of fewer than smaller ordinals) the answer is: almost anything. Easton's theorem (1970) shows that the function on regular cardinals can be prescribed arbitrarily in any model of ZFC, subject only to monotonicity…
Randomized algorithm analysis repeatedly estimates the fraction of inputs accepted by a Boolean computation. A formal theory of approximate counting specifies which assertions about those estimates can be used in a proof. Its strength matters when comparing probabilistic reasoning with combinatorial principles. Korten, Li, Oliveira and Ren study this…
First-order model checking asks, for a finite graph and a first-order sentence over the adjacency relation, whether . Problems such as -Dominating-Set, -Clique and -Subgraph-Isomorphism are instances. On general graphs the problem is believed not to be fixed-parameter tractable (fpt) in , since this is equivalent to …