Computational complexity
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.
153 records · Search and filter
- Math-1 P versus NP Problem
- Math-8 NP versus P/poly
- Math-9 NP versus coNP Problem
- Math-39 The Quantum PCP Conjecture
- Math-46 P vs. PSPACE
- Math-47 One-way functions exist
- Math-48 Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)
- Math-49 Unconditional Separation of BQP from the Polynomial Hierarchy
- Math-50 BQP Versus NP: Complete Language-Class Relation
- Math-51 P versus NP ∩ coNP
- Math-52 BQP versus QMA
- Math-53 NEXP versus P/poly
- Math-54 Permanent versus Determinant over C
- Math-55 Permanent–Determinant Separation Through Geometric Complexity Theory
- Math-56 Derandomization of Polynomial Identity Testing
- Math-58 Superlinear Circuit Lower Bounds for Explicit Boolean Functions
- Math-105 Planted Clique Conjecture
- Math-106 The Unique Games Conjecture
- Math-107 FPT versus W[1]
- Math-109 The Exponential Time Hypothesis for 3-SAT
- Math-110 Strong Exponential Time Hypothesis (SETH)
- Math-111 NP-Completeness of the Minimum Circuit Size Problem (MCSP)
- Math-113 The Log-Rank Conjecture
- Math-123 The NC versus P Problem for Efficient Parallel Computation
- Math-124 P vs. BPP
- Math-125 Basing One-Way Functions on NP-Hardness
- Math-127 Equivalence of Worst-Case and Average-Case Hardness for NP (Excluding Heuristica)
- Math-129 L = P Problem
- Math-131 P versus NC^1
- Math-134 Graph Isomorphism in Polynomial Time
- Math-136 PSPACE versus EXPTIME
- Math-138 L versus NL
- Math-150 QMA versus QCMA Problem
- Math-153 Unconditional Single-Prover Classical Verification of BQP Computations
- Math-169 NP versus the Existential Theory of the Reals
- Math-173 Derandomizing Space-Bounded Computation
- Math-179 Separation of P_R from NP_R in the Blum–Shub–Smale Model
- Math-181 Berman-Hartmanis Isomorphism Conjecture
- Math-193 Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication
- Math-231 Perfect-Matching Search in Deterministic NC (General Graphs)
- Math-252 Quantum versus Classical Communication Complexity of Total Functions
- Math-257 RL versus L
- Math-268 Classical Worst-Case Hardness Reduction for LWE
- Math-270 MAJORITY is not in ACC0
- Math-312 Unrestricted Linear-Circuit Lower Bound for the Discrete Fourier Transform
- Math-334 Worst-case to average-case hardness reduction for the Learning Parity with Noise problem
- Math-359 Existence of a p-Optimal Propositional Proof System
- Math-381 NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
- Math-416 Fourier Entropy-Influence Conjecture
- Math-1173 Complexity of square-root sum