P versus NP
A proposed guest list can be checked against the rules. Does easy checking always come with an efficient way to find a list that works?
Computational complexity
Within Computational complexity · Search all subjects
Unique Games conjecture
A special kind of constraint puzzle is predicted to remain hard even when almost all its rules can be satisfied.
Derandomization
Random choices help many algorithms run quickly. Can every efficient algorithm with a bounded error probability be replaced by an efficient deterministic one?
Quantum PCP conjecture
Can estimating a quantum system’s lowest energy remain computationally hard even when only a fixed amount of accuracy is required?
L versus NL
Can every computation that uses only logarithmic memory with nondeterministic choices be carried out using the same memory bound deterministically?
3SUM hypothesis
Can finding three integers with a specified additive relation be done faster than essentially quadratic time?
Online matrix–vector multiplication
Can a fixed Boolean matrix answer a sequence of arriving vectors in truly subcubic total time when each answer is needed before the next vector arrives?
Log-rank conjecture
Does the linear-algebraic rank of a Boolean table control how many bits two people must exchange to evaluate an entry?
Minimum Circuit Size Problem
Given every output of a Boolean function, how hard is it to decide whether a small circuit can produce that table?
Frege proof lower bounds
Can one exhibit propositional truths whose proofs must be superpolynomially long even in a flexible standard deductive system?
Strong Exponential Time Hypothesis
As satisfiability clauses become longer, does the best worst-case running-time exponent approach exhaustive search?
QMA versus QCMA
Does a quantum computer gain verification power when its certificate can be a quantum state rather than a classical string?
VP versus VNP
Can every polynomial described as a sum of efficiently computable terms itself be computed by a small arithmetic circuit?
Aaronson–Ambainis influence conjecture
Must a bounded low-degree polynomial that varies appreciably have an input bit with noticeable influence?
Polynomial hierarchy infinitude
Does each additional level of alternating computational choices add power, forever?
NP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?
Polynomial-time parity-game solving
Can the winner of every finite parity game be determined in polynomial time?
P versus PSPACE
Can every problem solvable with polynomial memory also be solved in polynomial time?
Hypergraph dualization
Can a classical polynomial-time algorithm recognize all minimal hitting sets?
Uniform-distribution PAC learning of DNF
Can ordinary random labeled examples teach a DNF formula in polynomial time under the uniform distribution?
Positivity problem for linear recurrences
Can an algorithm decide whether an integer sequence defined by a linear recurrence never becomes negative?
Deterministic NC perfect matching
Can a deterministic parallel algorithm find a perfect matching in every general graph with polylogarithmic time and polynomially many processors?
Deterministic polynomial identity testing
Can an algorithm efficiently determine, without random choices, whether an arithmetic circuit computes the zero polynomial?