Computer Science catalogue
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.
916 records · Search and filter
- CS-1 P versus NP Problem
- CS-2 NP versus P/poly
- CS-3 NP versus coNP Problem
- CS-4 The Quantum PCP Conjecture
- CS-5 P vs. PSPACE
- CS-6 One-way functions exist
- CS-7 Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)
- CS-8 Unconditional Separation of BQP from the Polynomial Hierarchy
- CS-9 BQP Versus NP: Complete Language-Class Relation
- CS-10 P versus NP ∩ coNP
- CS-11 BQP versus QMA
- CS-12 NEXP versus P/poly
- CS-13 Permanent versus Determinant over C
- CS-14 Permanent–Determinant Separation Through Geometric Complexity Theory
- CS-15 Derandomization of Polynomial Identity Testing
- CS-16 Superlinear Circuit Lower Bounds for Explicit Boolean Functions
- CS-17 Planted Clique Conjecture
- CS-18 The Unique Games Conjecture
- CS-19 FPT versus W[1]
- CS-20 The Exponential Time Hypothesis for 3-SAT
- CS-21 Strong Exponential Time Hypothesis (SETH)
- CS-22 NP-Completeness of the Minimum Circuit Size Problem (MCSP)
- CS-23 Capacity of the General Discrete Memoryless Relay Channel
- CS-24 The Log-Rank Conjecture
- CS-25 The NC versus P Problem for Efficient Parallel Computation
- CS-26 P vs. BPP
- CS-27 Basing One-Way Functions on NP-Hardness
- CS-28 Existence of One-Way Permutations
- CS-29 Equivalence of Worst-Case and Average-Case Hardness for NP (Excluding Heuristica)
- CS-30 L = P Problem
- CS-31 P versus NC^1
- CS-32 Graph Isomorphism in Polynomial Time
- CS-33 PSPACE versus EXPTIME
- CS-34 L versus NL
- CS-35 QMA versus QCMA Problem
- CS-36 Unconditional Single-Prover Classical Verification of BQP Computations
- CS-37 Polynomial pivot rule for the simplex method
- CS-38 Indistinguishability Obfuscation from Constant-Degree Homomorphic Assumptions
- CS-39 Asymptotic tightness of the binary Gilbert–Varshamov bound
- CS-40 NP versus the Existential Theory of the Reals
- CS-41 Randomized Integer Word-RAM 3SUM Conjecture
- CS-42 Derandomizing Space-Bounded Computation
- CS-43 Separation of P_R from NP_R in the Blum–Shub–Smale Model
- CS-44 Berman-Hartmanis Isomorphism Conjecture
- CS-45 Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups
- CS-46 Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication
- CS-47 Metric TSP Subtour LP Integrality Gap Conjecture
- CS-48 Polynomial Diameter Bounds for Polyhedra
- CS-49 Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- CS-50 Polynomial-Time Distribution-Free PAC Learning of DNF Formulas