Logic and computability
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. 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
- CS-20 The Exponential Time Hypothesis for 3-SAT
- CS-40 NP versus the Existential Theory of the Reals
- CS-54 Exact satisfiability threshold for random k-SAT for small k (k = 3)
- CS-62 Polynomial-Time Decidability of Semidefinite Programming Feasibility
- CS-65 Bodirsky-Pinsker Tractability Conjecture for Infinite-Domain Constraint Satisfaction
- CS-73 Existence of a p-Optimal Propositional Proof System
- CS-76 Computability of the Shannon Capacity of Finite Graphs
- CS-112 Decidability of Rational Points over Number Fields
- CS-131 Counting-hierarchy upper bound for existential-universal real sentences
- CS-184 Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
- CS-266 Expected-Optimum Approximation for Random MAX $R$-3SAT
- CS-296 Decidability of Simplicial-Complex Embeddability
- CS-308 Decidability of Universal Factor Languages
- CS-318 Decidability and Finiteness of Rational Joint Spectral Radii
- CS-345 Resolution Lower Bounds for Clique Certification
- CS-395 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- CS-400 Decidability of Linear Information Inequalities
- CS-406 Enumeration and Typical Structure of $k$-SAT Functions
- CS-407 Asymptotic Counts of Growing-Width $k$-SAT Functions
- CS-417 Superpolynomial Lower Bounds for Dag-Like Resolution over Parities
- CS-418 Fractional Coefficient Savings in Algebraic Proof Systems
- CS-437 Degree Automatability of Sum-of-Squares Proofs
- CS-569 Ordered proof traces for sound educational interoperability
- CS-671 Predicting SAT-Solver Hardness from Formula Structure
- CS-694 Refutation Lower Bounds for Random k-SAT Instances
- CS-702 Cutting Planes Lower Bounds for Random CNF Formulas
- CS-704 Random CNF Lower Bounds beyond Cutting Planes
- CS-740 Computable Neural-Network Approximation from Noisy Samples
- CS-741 Computable Ground Truths for Learning Problems
- CS-744 Constraint-Satisfaction Table Caption
- CS-754 Enumeration and Sparsity of Growing-$k$ SAT Functions
- CS-762 Open Problems in Proof and Computational Complexity
- CS-763 Coefficient Compression and Structured Proof-System Lower Bounds
- CS-767 Lower Bounds for Polynomial Calculus with Inverses
- CS-773 Abelian Embeddings and Gap-CSP Integrality Gaps
- CS-798 Decidability of Symmetric Polynomial Nonnegativity