Is the rank of the communication matrix, on a logarithmic scale, essentially the whole story of deterministic communication complexity? Open since the late 1980s.
The Problems
Not schoolwork — the questions that resisted Erdős, Hilbert, and everyone since. The club keeps three shelves: what is still open, what AI recently settled, and what took humanity centuries.
Tagged complexity-theory — 5 entries. Clear
Valiant's Hypothesis
open
The permanent needs superpolynomial arithmetic circuits (VP ≠ VNP). Algebraic complexity's founding question, open since 1979.
All NP-complete problems are the same problem up to polynomial-time recoding. Open since 1977; a positive answer would reveal deep structure in NP.
Does BPP = P?
open
Is randomness essential to efficient computation? BPP = P would follow from strong circuit lower bounds; unconditionally, the question is wide open.
P versus NP
open
If a solution can be checked quickly, can it also be found quickly? The question that organises theoretical computer science.