3 ms·
From Scott Aaronson's blog post on the paper: > Basically, they need to show that, for every k, there are problems that can be solved by small circuits with k
by _asummers 12y ago
From Scott Aaronson's blog post on the paper:
> Basically, they need to show that, for every k, there are problems that can be solved by small circuits with k layers of AND, OR, and NOT gates, but for which the answer can’t even be guessed, noticeably better than chance, by any small circuit with only k-1 layers of AND, OR, and NOT gates.