Computational complexity
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.
153 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-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-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-40 NP versus the Existential Theory of the Reals
- 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-46 Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication
- CS-52 Perfect-Matching Search in Deterministic NC (General Graphs)
- CS-55 Quantum versus Classical Communication Complexity of Total Functions
- CS-57 RL versus L
- CS-60 Classical Worst-Case Hardness Reduction for LWE
- CS-61 MAJORITY is not in ACC0
- CS-68 Unrestricted Linear-Circuit Lower Bound for the Discrete Fourier Transform
- CS-71 Worst-case to average-case hardness reduction for the Learning Parity with Noise problem
- CS-73 Existence of a p-Optimal Propositional Proof System
- CS-74 NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
- CS-77 Fourier Entropy-Influence Conjecture
- CS-90 Complexity of square-root sum