QMA versus QCMA
Does a quantum computer gain verification power when its certificate can be a quantum state rather than a classical string?
Computer science
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?
Deterministic prime construction
Can an algorithm reliably construct a prime of any requested bit length in polynomial time without randomness?
Polynomial hierarchy infinitude
Does each additional level of alternating computational choices add power, forever?
Metric TSP subtour integrality gap
How much can the best traveling-salesperson tour cost exceed its standard fractional relaxation in the worst metric instance?
NP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Small-Set Expansion hypothesis
Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?
Densest-k-subgraph approximation
Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?
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?
Černý conjecture
Can every synchronizing n-state automaton be reset with at most (n−1)² input symbols?
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?
Bag containment of conjunctive queries
Can an algorithm decide whether one database query always produces each answer no more often than another?
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?
Explicit linear circuit lower bounds
Can we explicitly construct binary matrices whose linear maps require more than a constant number of XOR gates per input?
P versus NC
Can every decision problem with a polynomial-time sequential algorithm also be solved with polynomial-size parallel circuits of polylogarithmic depth?
Exact edit-distance complexity
Can the exact number of edits between two strings be computed in O(n^(2−ε)) worst-case time for some fixed ε > 0?
Binary deletion channel capacity
What is the exact reliable information rate when bits disappear independently and the receiver cannot see where they were removed?
Directed feedback vertex set approximation
Can a polynomial-time algorithm remove all directed cycles while deleting at most a fixed multiple of the minimum possible vertex cost?