Strong Exponential Time Hypothesis
As satisfiability clauses become longer, does the best worst-case running-time exponent approach exhaustive search?
Computer science
Within Computer science · Search all subjects
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?
Fourier Entropy–Influence conjecture
Does a yes-or-no rule’s sensitivity to flipped inputs limit how widely its Fourier weight can spread?
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?
High-precision analog in-memory computing
Several methods correct errors in analog memory calculations. How should they be combined when inputs, noise and conversion costs change?
Vaught’s conjecture
Can a complete countable theory have an intermediate number of countable models?
Č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?