Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Mathematical Logic

78 missions · 48 completed

Missions

Open30Completed48All78
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: Rizwan G Mir

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.

175 thms9 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

Horn Maximum Satisfiability: Reductions, Algorithms and Applications: SAT reduces to Horn MaxSAT by dual-rail encodingResearch Paper

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…

19 thms6 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer ScienceTopology·Captain: Shuze Chen

Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper

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…

31 thms5 active usersReviewed
Category TheoryComplexity TheoryGraph Theory·Captain: iris

Co-Decompositions and FO Model CheckingResearch Paper

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…

34 thms5 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

A Uniform Algorithm for Strict NP on Bounded-Treedepth StructuresResearch Paper

Strict NP (SNP) is the class of properties of finite structures expressible as ∃R1…Rr ∀x1…xk ψ\exists R_1\dots R_r\,\forall x_1\dots x_k\,\psi∃R1​…Rr​∀x1​…xk​ψ with ψ\psiψ 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 kkk, whether its twin-width is at most kkk, or whether it is ccc-colour…

31 thms5 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

On efficient global updates in first-order logicResearch Paper

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,…

25 thms4 active usersReviewed
Computational Complexity·Captain: mikedeng1

Parallelism and Adaptivity in Student-Teacher WitnessingResearch Paper

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…

58 thms4 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Model Checking for Metric Extensions of Monadic Second-Order LogicResearch Paper

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 f(∣φ∣+tw(G))NO(1)f(|\varphi|+\mathrm{tw}(G))N^{O(1)}f(∣φ∣+tw(G))NO(1) (Courcelle 1992; Arnborg, Lagergren, Seese 1991). Optimization and counting versions followed (Courcelle, Mosbah 1993), as did…

49 thms4 active usersReviewed
🏆Completed
Theory of Computation·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 2: Without the Size 1^|M| a Simulator with Oracle Access to ⟨M⟩ Cannot Decide Every Decidable Promise Problem Closed under Functional EquivalenceResearch Paper

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…

11 thms4 active usersReviewed
Algorithmic Game TheoryProbability·Captain: martelus trismortuus

Online problems as Abramsky–Jagadeesan games: memoryless 2-taxi is not competitiveOpen Problem

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 kkk-taxi problem, optimal stopping and prophet inequalities, bandits. Each defines its own players, strategies and adversaries from scratch. For example, …

27 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Backdoors for Quantified Boolean FormulasResearch Paper

A quantified Boolean formula (QBF) Φ=Q.ϕ\Phi = Q.\phiΦ=Q.ϕ quantifies every variable of a Boolean matrix ϕ\phiϕ by a prefix Q=Q1x1⋯QnxnQ = Q_1x_1\cdots Q_nx_nQ=Q1​x1​⋯Qn​xn​, Qi∈{∀,∃}Q_i\in\{\forall,\exists\}Qi​∈{∀,∃}. 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.

23 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: utkuokur

Ten Challenges 06: Better-quasi-ordering of finite graphs under minorsOpen Problem

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…

23 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: utkuokur

Ten Challenges 10: Unfriendly partition conjectureOpen Problem

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…

10 thms3 active usersReviewed
🏆Completed
Category TheoryTheoretical Computer ScienceType Theory·Captain: kmehltretter82

The Groupoid Model Refutes Uniqueness of Identity ProofsResearch Paper

In dependent type theory, a proof of equality is itself a mathematical object. If two objects a,b:Aa,b:Aa,b:A are equal, the identity type IdA(a,b)\mathrm{Id}_A(a,b)IdA​(a,b) 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…

7 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: kmehltretter82

Multivariate Amortised Resource Analysis for Term Rewrite SystemsResearch Paper

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…

10 thms3 active usersReviewed
🏆Completed
Model Theory·Captain: LG

Continuum Hypothesis: Independence from ZFCTextbook

The continuum hypothesis (CH) asks how large the set of real numbers is. Cantor proved that ∣Z∣=∣Q∣<∣R∣|\mathbb Z|=|\mathbb Q|<|\mathbb R|∣Z∣=∣Q∣<∣R∣, 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…

33 thms3 active usersReviewed
🏆Completed
Captain: LG

Singular Cardinals Hypothesis: Silver's reduction to countable cofinalityTextbook

Cantor's continuum problem asks for the value of 2κ2^\kappa2κ, the cardinality of the power set of an infinite cardinal κ\kappaκ. For regular cardinals ZFC says almost nothing: by Easton's theorem (1970) the function κ↦2κ\kappa\mapsto 2^\kappaκ↦2κ on regular cardinals can be essentially any non-decreasing function with cf⁡(2κ)>κ\operatorname{cf}(2^\kappa)>\kappacf(2κ)>κ. For singular card…

14 thms3 active usersReviewed
🏆Completed
Theory of Computation·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 1: A Decidable Promise Problem Closed under Functional Equivalence Is Decided by a Simulator Given Only Oracle Access to ⟨M⟩ and the Size 1^|M|Research Paper

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…

8 thms3 active usersReviewed
🏆Completed
Number Theory·Captain: marwahaha

Single-fold Diophantine representationsOpen Problem

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.

48 thms3 active usersReviewed
🏆Completed
Model Theory·Captain: wurtle

A CH obstruction to a prescribed categoricity thresholdResearch Paper

A class of structures is categorical in a cardinal λ\lambdaλ if it has exactly one model of size λ\lambdaλ 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,…

26 thms3 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper

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…

13 thms3 active usersReviewed
🏆Completed
Topology·Captain: LG

Acharjee–Gogoi: Cognitive-Consequence Spaces and the Limit of Human IntelligenceResearch Paper

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…

14 thms3 active usersReviewed
🏆Completed
Captain: LG

Jech Set Theory I: Silver's Theorem on Singular CardinalsTextbook

How large can the power set of an infinite set be? For a regular cardinal κ\kappaκ (one that is not the supremum of fewer than κ\kappaκ smaller ordinals) the answer is: almost anything. Easton's theorem (1970) shows that the function κ↦2κ\kappa \mapsto 2^{\kappa}κ↦2κ on regular cardinals can be prescribed arbitrarily in any model of ZFC, subject only to monotonicity…

7 thms3 active usersReviewed
Computational Complexity·Captain: mikedeng1

Approximate Counting and the Provability of Combinatorial PrinciplesResearch Paper

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…

17 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

First-Order Model Checking on Monadically Dependent Graph ClassesResearch Paper

First-order model checking asks, for a finite graph GGG and a first-order sentence φ\varphiφ over the adjacency relation, whether G⊨φG\models\varphiG⊨φ. Problems such as kkk-Dominating-Set, kkk-Clique and HHH-Subgraph-Isomorphism are instances. On general graphs the problem is believed not to be fixed-parameter tractable (fpt) in ∣φ∣|\varphi|∣φ∣, since this is equivalent to …

38 thms2 active usersReviewed
PreviousPage 1 of 4Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me