Logic and computability
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
36 records · Search and filter
- Math-109 The Exponential Time Hypothesis for 3-SAT
- Math-169 NP versus the Existential Theory of the Reals
- Math-250 Exact satisfiability threshold for random k-SAT for small k (k = 3)
- Math-273 Polynomial-Time Decidability of Semidefinite Programming Feasibility
- Math-296 Bodirsky-Pinsker Tractability Conjecture for Infinite-Domain Constraint Satisfaction
- Math-359 Existence of a p-Optimal Propositional Proof System
- Math-412 Computability of the Shannon Capacity of Finite Graphs
- Math-2349 Decidability of Rational Points over Number Fields
- Math-2973 Counting-hierarchy upper bound for existential-universal real sentences
- Math-4373 Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
- Math-4455 Expected-Optimum Approximation for Random MAX $R$-3SAT
- Math-4485 Decidability of Simplicial-Complex Embeddability
- Math-4497 Decidability of Universal Factor Languages
- Math-4507 Decidability and Finiteness of Rational Joint Spectral Radii
- Math-4534 Resolution Lower Bounds for Clique Certification
- Math-4584 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- Math-4589 Decidability of Linear Information Inequalities
- Math-4595 Enumeration and Typical Structure of $k$-SAT Functions
- Math-4596 Asymptotic Counts of Growing-Width $k$-SAT Functions
- Math-4606 Superpolynomial Lower Bounds for Dag-Like Resolution over Parities
- Math-4607 Fractional Coefficient Savings in Algebraic Proof Systems
- Math-4626 Degree Automatability of Sum-of-Squares Proofs
- Math-5104 Ordered proof traces for sound educational interoperability
- Math-5206 Predicting SAT-Solver Hardness from Formula Structure
- Math-5229 Refutation Lower Bounds for Random k-SAT Instances
- Math-5237 Cutting Planes Lower Bounds for Random CNF Formulas
- Math-5239 Random CNF Lower Bounds beyond Cutting Planes
- Math-5275 Computable Neural-Network Approximation from Noisy Samples
- Math-5276 Computable Ground Truths for Learning Problems
- Math-5279 Constraint-Satisfaction Table Caption
- Math-5289 Enumeration and Sparsity of Growing-$k$ SAT Functions
- Math-5297 Open Problems in Proof and Computational Complexity
- Math-5298 Coefficient Compression and Structured Proof-System Lower Bounds
- Math-5302 Lower Bounds for Polynomial Calculus with Inverses
- Math-5308 Abelian Embeddings and Gap-CSP Integrality Gaps
- Math-5333 Decidability of Symmetric Polynomial Nonnegativity