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: mikedeng1

Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper

A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…

30 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: iris

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]\mathsf{AC}^0[2]AC0[2]-FregeResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR and parity (XOR) gates. Superpolynomial lower bounds for the corresponding circuit class have been known since Razborov and Smolensky (1987) (Razborov 1987, Smolensky 1987), but carrying these techniques over to proofs has been open since the 1990s (Be…

64 thms2 active usersReviewed
🏆Completed
AlgebraModel TheoryPure Mathematics·Captain: Alien60

Barto-Kozik: Absorbing Subalgebras and Cyclic TermsResearch Paper

A constraint satisfaction problem CSP(A)\mathrm{CSP}(\mathbb A)CSP(A) asks whether a given conjunction of constraints, each a relation of a fixed finite structure A\mathbb AA, has a solution. The algebraic approach to its complexity studies the polymorphisms of A\mathbb AA, the operations preserving all of its relations. Bulatov, Jeavons and Krokhin (SIAM J. Comput. 2005)…

13 thms2 active usersReviewed
🏆Completed
AlgebraPure Mathematics·Captain: Alien60

Function Algebras on Finite Sets I: Pol-Inv Galois Connection and the Baker-Pixley TheoremTextbook

A clone on a set AAA is a set of finitary operations that contains all projections and is closed under composition; the term operations of any algebra form a clone. Relations give a dual description: an operation fff preserves an hhh-ary relation R⊆AhR\subseteq A^hR⊆Ah if applying fff coordinatewise to tuples of RRR always lands in RRR. The maps Pol\mathrm{Pol}Pol (operations…

9 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: iris

Progress on AC0[2]-Frege Lower BoundsResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by…

36 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
🏆Completed
Theoretical Computer ScienceType Theory·Captain: kmehltretter82

Type-Based Termination Checking in AgdaResearch Paper

A proof assistant based on type theory has to reject non-terminating definitions: a function that loops can inhabit any type, including the empty one, and so proves everything. Agda therefore checks every recursive definition for termination before accepting it. Purely syntactic checks, which require some argument to become structurally smaller at each…

30 thms2 active users
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
🏆Completed
Formal VerificationTheory of Computation·Captain: mikedeng1

Monitoring Metric First-Order Temporal Properties: The Monitor M_Φ Outputs Exactly the Violations (¬Φ)^(D̄,τ̄,i) of a Bounded MFOTL Formula Φ, as Regular Sets, at Every Time Point iResearch Paper

Runtime monitoring checks a running system against a specification by inspecting its trace of events as it is produced. Policies on data, such as "every published report was approved within the last 10 days" or "each value stored in in reaches out within 5 time units", quantify over data values and constrain the time between events. Metric first-order…

14 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: marwahaha

Relative independence of the separable quotient problemOpen Problem

The separable quotient problem asks whether every infinite-dimensional Banach space admits a separable infinite-dimensional quotient. The selected statement isolates a negative result under the continuum hypothesis. The pinned manuscript supplies the research context.

5 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: marwahaha

A counterexample to Naimark's problem in ZFCOpen Problem

Uniqueness of irreducible representations is a strong condition on a C*-algebra. The target asks for a counterexample to the expected compact-operator characterization without added set-theoretic hypotheses. The pinned manuscript supplies the research context.

3 thms2 active usersReviewed
🏆Completed
Captain: marwahaha

The Partition Principle does not imply ChoiceOpen Problem

The Partition Principle reverses the cardinal comparison provided by a surjection without requiring a section. The source studies whether this weaker form of comparison can hold while full Choice fails. The source is OpenAI's September 2026 manuscript.

24 thms2 active usersReviewed
🏆Completed
Algebra·Captain: marwahaha

Finite congruence lattices: characterization and undecidabilityOpen Problem

A finite algebra has a lattice of congruences, ordered by inclusion. The source studies which finite lattices arise in this way, and the available goal captures its colored-graph characterization. The source is OpenAI's September 2026 manuscript.

4 thms2 active usersReviewed
🏆Completed
Algebraic TopologyGroup Theory·Captain: wurtle

Simple F∞ overgroups of groups with decidable word problemResearch Paper

A finitely generated group has decidable word problem if an algorithm decides, for every word in a fixed finite generating set and its inverses, whether it represents the identity. Embedding theorems translate this algorithmic property into algebra: Higman (1961) characterized subgroups of finitely presented groups, and Boone and Higman (1974) showed that…

6 thms2 active usersReviewed
🏆Completed
AlgebraGroup Theory·Captain: wurtle

Finite algebraic envelopes and the Boone–Higman conjectureResearch Paper

The word problem for a group with a finite generating set asks whether a given word in the generators and their inverses represents the identity; it is decidable if one algorithm answers this for every word. Since Higman's embedding theorem (1961), a recurring theme in combinatorial group theory has been to characterize algorithmic properties of groups by…

13 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

Weak and strong normalization in pure type systemsResearch Paper

Pure type systems (PTSs) are a uniform framework covering the simply typed λ-calculus, System F, the calculus of constructions and the type theories behind proof assistants such as Coq and Lean. A system is specified by its sorts (like ∗\ast∗ and □\square□), axioms (∗:□\ast:\square∗:□) and product rules (which dependent function types may be formed). Normalization is…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Witnessed symmetric choice is strictly stronger than choiceless polynomial time with countingResearch Paper

A logic for unordered finite structures (graphs, databases, relational inputs given up to isomorphism) must give answers that do not depend on how the input elements are named. Many polynomial-time algorithms nevertheless make arbitrary intermediate choices, for example the pivot in Gaussian elimination, without changing their final answer. Choiceless…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Choiceless polynomial time with counting does not capture polynomial timeResearch Paper

Descriptive complexity asks whether complexity classes can be characterized by logics, without reference to machines. Immerman and Vardi (1982) showed that on ordered finite structures, first-order logic with a least fixed-point operator expresses exactly the polynomial-time queries. On unordered structures, such as graphs given only up to isomorphism, an…

4 thms2 active usersReviewed
🏆Completed
Theory of Computation·Captain: wurtle

Rigidity of the Turing degreesResearch Paper

Turing reducibility compares sets of natural numbers by their information content: A≤TBA\le_TBA≤T​B if an oracle Turing machine with oracle BBB computes the characteristic function of AAA. Identifying mutually reducible sets gives the Turing degrees DT\mathcal D_TDT​, partially ordered by ≤T\le_T≤T​. A central question of computability theory since the 1970s is how much of the…

27 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: wurtle

Computing the Random 3-SAT ThresholdResearch Paper

Random 3-SAT, a conjunction of random three-literal clauses on nnn variables, is the classic test case for the typical behavior of satisfiability. Experiments placed the hardest instances near the density where half the formulas are satisfiable, and statistical physics predicts a sharp satisfiability threshold near 4.2674.2674.267. Once a limiting threshold α3\alpha_3α3​ is…

20 thms2 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: wurtle

Generalized Star Height at Most ThreeResearch Paper

A regular expression describes a set of words using letters, union, concatenation and the Kleene star P∗P^*P∗ (any finite repetition of words from PPP). The star height of an expression is the depth of nesting of its stars, and it measures how many layers of unbounded repetition a regular language genuinely needs. For ordinary expressions this hierarchy is…

2 thms2 active usersReviewed
🏆Completed
Complexity TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

The Complexity of Markov Decision Processes V: A Quantified Boolean Formula Is True Iff Its Partially Observed Markov Decision Process Has a Zero-Cost PolicyResearch Paper

A Markov decision process is the standard model of sequential decision making under uncertainty: a controller observes the state of a finite system, chooses a decision, pays a cost, and the system moves to a random next state. In many applications (maintenance, inventory with unreliable records, robotics, medical treatment) the controller does not see the…

8 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
PreviousPage 2 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