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
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
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
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
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Monadically Dependent Graph Classes Have Almost Bounded Merge-WidthResearch Paper

First-order model checking asks, given a graph GGG and a first-order sentence φ\varphiφ, whether φ\varphiφ holds in GGG. A central conjecture states that this problem is fixed-parameter tractable on every monadically dependent graph class: a class that cannot encode all graphs through a fixed formula over vertex-colored members. Planar graphs, classes of bounded…

41 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Relational Queries Computable in Polynomial Time: On Ordered Databases, Relational Calculus with One Least Fixpoint Expresses Exactly the Polynomial-Time QueriesResearch Paper

Relational calculus, the first-order query language of relational databases (Codd, 1972), cannot express the transitive closure of a relation, so "is xxx an ancestor of yyy?" is not a first-order query (Aho and Ullman, 1979). Aho and Ullman proposed adding a least fixpoint operator (LFP). Chandra and Harel (1980) studied the resulting Fixpoint Hierarchy and…

19 thms2 active usersReviewed
Complexity Theory·Captain: LG

F_d versus F_{d+1}: fixed-depth separation of bounded-depth FregeOpen Problem

Bounded-depth Frege systems are the proof systems of propositional logic in which every formula of a proof has depth bounded by a fixed constant ddd; the resulting system is written FdF_dFd​. They are the proof-theoretic counterpart of the circuit class AC0\mathrm{AC}^0AC0 and of the bounded arithmetic theories IΔ0I\Delta_0IΔ0​ and its relatives: short FdF_dFd​-proofs of a family…

6 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 5: First-Order Interpretations of a Class of Graphs of Bounded Twin-width Have Bounded Twin-widthResearch Paper

Twin-width is a graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant in Twin-width I: Tractable FO Model Checking (J. ACM 69(1), Article 3, 2021; arXiv:2004.14789). Its main algorithmic consequence is that first-order model checking is fixed-parameter tractable on graphs given with a contraction sequence of bounded width. A parameter of this…

15 thms2 active usersReviewed
Combinatorics·Captain: LG

Erdős Problem 592: which ω^β are partition ordinals?Open Problem

Ramsey's theorem says that every red/blue colouring of the pairs of an infinite set has an infinite monochromatic subset. For well-ordered sets one can ask for more: the monochromatic set should have the same order type as the whole set. Erdős and Rado introduced the partition relation α→(β,c)2\alpha \to (\beta, c)^2α→(β,c)2 to measure exactly this, and asked which…

8 thms2 active usersReviewed
Theoretical Computer Science·Captain: LG

Navier–Stokes Lost in Translation: SCI = ∞ for faithful autoformalisationResearch Paper

Autoformalisation translates a natural-language mathematical text into a formal language such as Lean 4 so a proof assistant can check it. It is increasingly used to "verify" AI-produced mathematics, notably announced AI proofs of blow-up for the Navier–Stokes and Euler equations. Bastounis, Circelli and Hansen (arXiv:2610.08144) show that a Lean…

10 thms1 active userReviewed
Type Theory·Captain: kmehltretter82

Higher Type Recursion, Ramification and Polynomial TimeResearch Paper

How can recursion on notation in all finite types (as in Gödel's System TTT) be restricted so that the definable first-order functions are precisely the polynomial-time computable functions? As Bellantoni, Niggl, and Schwichtenberg observe in the introduction to their 2000 Annals of Pure and Applied Logic paper, ramification of the recursion variable alone is…

9 thms1 active userReviewed
Captain: LG

The Kunen inconsistency without Choice: does ZF\mathrm{ZF}ZF refute Reinhardt cardinals?Open Problem

The large cardinal hierarchy of modern set theory — inaccessible, measurable, supercompact, extendible — is organized by elementary embeddings j:V→Mj : V \to Mj:V→M whose target MMM approximates the universe VVV ever more closely. In 1967 William Reinhardt proposed the natural limit of this trend: a nontrivial elementary embedding j:V→Vj : V \to Vj:V→V of the universe into itself,…

8 thms1 active userReviewed
Complexity TheoryMachine LearningTheoretical Computer Science·Captain: Shuze Chen

A Witnessing Duality for ReLU Network DepthResearch Paper

How many hidden layers a ReLU network needs to compute max⁡(x1,…,xn)\max(x_1,\dots,x_n)max(x1​,…,xn​) exactly is a basic question about the expressiveness of depth. Exact representation questions of this kind are studied for real, rational and integer weights. For integer weights, Haase, Hertrich and Loho (arXiv:2302.12553) proved a logarithmic depth lower bound by a modular argument…

7 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler–Leman and Hypertree WidthResearch Paper

The Weisfeiler–Leman (WL) family of colour-refinement algorithms is the standard heuristic for graph isomorphism and the yardstick for the expressive power of graph neural networks. Its distinguishing power has an exact algebraic description: by Lovász's theorem two graphs are isomorphic iff every graph has the same number of homomorphisms into both, and…

22 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

The Metacomplexity Structure of Search ProblemsResearch Paper

Metacomplexity studies the complexity of computational tasks that are themselves about computation: compressing strings, estimating circuit complexity, or refuting a claimed algorithm by finding an input on which it fails. Refutation tasks appear in learning theory, in hardness magnification, in derandomization and in bounded arithmetic. A refutation task…

21 thms1 active userReviewed
Computational ComplexitycryptographyTheoretical Computer Science·Captain: Shuze Chen

Fine-Grained Proof Complexity for Elementary Arithmetic in Extended FregeResearch Paper

Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…

18 thms1 active userReviewed
Complexity Theory·Captain: iris

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of RelationsResearch Paper

Tarski showed in the 1940s that, over binary relational signatures, three-variable first-order logic (FO3\mathrm{FO}^3FO3) and the calculus of relations (CoR), a variable-free algebra of binary relations, define the same binary queries (Tarski 1941; Tarski–Givant 1987). The two translations are lopsided: a CoR term TTT becomes an FO3\mathrm{FO}^3FO3 formula of size O(∣T∣)O(|T|)O(∣T∣)…

22 thms1 active userReviewed
Control TheoryDynamical SystemsTheoretical Computer Science·Captain: Shuze Chen

Global asymptotic stability of homogeneous polynomial vector fields is undecidableResearch Paper

A differential equation can have a simple finite description while its solutions have complicated long-term behavior. In control theory, one basic question is whether every state eventually approaches an equilibrium and whether starting close to it guarantees remaining close. An algorithm answering that question for every polynomial vector field would…

22 thms1 active userReviewed
PreviousPage 1 of 2Next

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