This months favorite theorem is a circuit result that implies the polynomial-time hierarchy is infinite relative to a random oracle, answering an open question that goes back to the 80's.
Johan Håstad, Benjamin Rossman, Rocco A. Servedio and Li-Yang Tan
The authors show how to separate depth d from depth d+1 circuits for random inputs. As a corollary, the polynomial hierarchy is infinite with a random oracle, which means that if we choose an oracle R at random, with probability one, the k+1-st level of the polynomial-time hierarchy relative to R is different than the k-th level relative to R.
Why should we care about random oracles? By the Kolmogorov zero-one law, every complexity statement holds with probability zero or probability one with a random oracle, so for every statement either it or its negation holds with probability one. And since the countable intersection of measure-one sets is measure one, every complexity statement true relative to a random oracle are all simultaneously true relative to a random oracle, a kind of consistent world. With a random oracle, we have full derandomization, like BPP = P, AM = NP and PH in \(\oplus\mathrm{P}\). We have separations like P ≠ UP ≠ NP. We have results like NP doesn't have measure zero and SAT solutions can be found with non-adaptive queries to an NP oracle. And now we have that the PH is infinite simultaneously with all these other results.
More details on this paper from a post I wrote back in 2015.
(Bill- Gee, we can separate PH with a random oracle but we still can't adjust the setting so that I can post without being moderated. And this is not a Luddite thing- Non-Luddite Lance could not figure it out either.)
ReplyDeleteWas this a circuit result or an oracle result? Actually it was, as is typical, a circuit result that implied an oracle result. But which do we care about? If some theorem in hard math implied P NE NP the then would the title be
The p-adic cohomology of finite genus curves is prime
or
P NE NP. Really!
I did a post about oracle result vs circuit result here:
https://blog.computationalcomplexity.org/2015/04/the-new-oracle-result-new-circuit.html
Also relevant:
https://www.nbc.com/saturday-night-live/video/shimmer-floor-wax/2721424
It wouldn't have made my favorite list without the oracle result.
Delete