Proofs and certificates
Which statements have short proofs, and how do proof methods compare?
3 problemsLimits of computation
Algorithms, computational limits and the guarantees behind decisions.
Subjects: Computational complexity · Algorithms and data structures
Explore this collection
Computing with graphs
Graph structure, approximation, counting and coordination across a network.
11 problemsLinear recurrences
Two different decisions about recurrence sequences: whether a zero occurs and whether all terms are nonnegative.
2 problemsInformation and coding
The capacity and reliability of communication through noise, deletions and networks.
5 problemsCryptography
Encryption, program obfuscation and the assumptions behind computational secrecy.
4 problemsGames and strategies
Perfect play in chess, winners in graph games, and pursuit strategies.
3 problemsProblems in this collection
24 problemsP 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?
L versus NL
Can every computation that uses only logarithmic memory with nondeterministic choices be carried out using the same memory bound deterministically?
Graph isomorphism complexity
Two graphs can look different because their vertices have different names. Can we always decide efficiently whether they have the same connections?
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?
Polynomial hierarchy infinitude
Does each additional level of alternating computational choices add power, forever?
P versus PSPACE
Can every problem solvable with polynomial memory also be solved in polynomial time?
Deterministic prime construction
Can an algorithm reliably construct a prime of any requested bit length in polynomial time without randomness?
Aaronson–Ambainis influence conjecture
Must a bounded low-degree polynomial that varies appreciably have an input bit with noticeable influence?
Bag containment of conjunctive queries
Can an algorithm decide whether one database query always produces each answer no more often than another?
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?
Pure subtype system type safety
A type system can let programs and their types share the same language. Can the remaining proof show that the proposed pure-subtype rules stay valid as a program evaluates?
Rabin–Mostowski index problem
A finite automaton can check an infinite branching tree using a hierarchy of recurring priorities. Can an algorithm tell whether the same trees can be recognized with a smaller priority hierarchy?
Integer multiplication complexity
Long multiplication can be improved to O(n log n) bit operations. Is that logarithmic overhead unavoidable, or could multiplying arbitrary n-bit integers get closer to linear time?
Online bin packing competitive ratio
Items arrive one at a time and must be placed immediately into unit-capacity bins. What is the smallest guaranteed long-run overhead compared with packing the whole list after seeing it?