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?
Computer science
Within Computer science · Search all subjects
Mechanistic interpretability
We can inspect a neural network's numbers without understanding its computation. Can explanations become reliable enough to predict and check its behavior?
AI alignment
Alignment asks how AI systems can reliably follow intended goals and constraints, including in situations different from those used in training.
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?
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?
Matrix multiplication exponent
Multiplying two square matrices seems to require more work than writing their answer. Is the best possible asymptotic exponent actually two?
Classical integer factorization
77 = 7 × 11 is easy to check. Can a classical computer find the complete prime factorization of every integer efficiently as its written length grows?
One-way functions
Can a function be easy to compute but hard to reverse on typical inputs? A rigorous unconditional example is still missing.
Skolem problem
A sequence follows a fixed linear recurrence. Is there an algorithm that always decides whether any term of the sequence equals zero?
Quantum PCP conjecture
Can estimating a quantum system’s lowest energy remain computationally hard even when only a fixed amount of accuracy is required?
All-pairs shortest paths complexity
Can exact shortest-path distances between every pair of vertices in a general weighted graph be computed in truly subcubic time?
Splay tree dynamic optimality
A splay tree reorganizes itself after searches. Is its total cost always within a constant factor of the best search tree that knows all requests in advance?
L versus NL
Can every computation that uses only logarithmic memory with nondeterministic choices be carried out using the same memory bound deterministically?
Continual learning
An AI system can learn new tasks and lose skills it already had. How can it keep useful knowledge while adapting with limited memory and computation?
Out-of-distribution generalization
A model can predict well on familiar data and fail when conditions change. Which changes can it handle reliably, and how can we know?
Adversarial robustness
Carefully chosen changes to an input can fool a learned classifier. How can we provide reliable protection against a stated class of such changes?
Machine unlearning
Can a trained model efficiently remove the influence of selected training data, with credible evidence of what was removed?
Hilbert’s tenth problem over the rationals
Can an algorithm always decide whether an equation with integer coefficients has a solution made of rational numbers?
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?