Polynomial-Time Hierarchy Is Infinite Under a Random Oracle | Hacker News Reader

Polynomial-Time Hierarchy Is Infinite Under a Random Oracle

blog.computationalcomplexity.org

34 points2510c39011c511 comments

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.

I'm struggling to understand the concept of a "random oracle". I assume any oracle is just an infinite string of bits, or natural numbers, or suchnot, and thus is countably infinite (and has order omega), so there would be uncountably many (2^aleph-null) such oracles - how does one pick one at random, such that they are (I assume) equally likely? How does one pick a random element from an uncountable set?

And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

>And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

Almost surely not

So then, their result isn't certainly true, only almost surely true?

"with probability 1" is a fairly standard phrasing that is equivalent to infinitesimally-small probability (e.g., a more precise statement might be: the set of oracles where the result is not true has "zero Lebesgue measure" -- I haven't checked to see exactly what formal statement they use).

An oracle would be a sequence that give you a correct answer to a problem (or set of problems).

You could use Kolmogorov randomness to say whether this sequence is also random: "Kolmogorov randomness – also called algorithmic randomness – defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string."

http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

How do you identify the length of a program to determine that? If I had a presumably random string and an assembly dialect that had a command that outputs that exact string, the 'program' has been deferred to the hardware or the brain of its inventor. I can understand how that is still a long program, but I can't understand how that would be measured.

Kolmogorov complexity is not a single value - it's more of a function f(universal computer, string) -> <minimal length of program to output that string>.

It of course depends on the "assembly dialect". But given any two "assembly dialects" A1 and A2 their respective "length functions" f1 and f2 produce the same result, up to a constant. The idea is that you can write an emulator of A2 in A1 - code of constant length.

Theorems 1 and 3 are finitary and easier to physically interpret. As for Theorem 2, "With probably p a random foo has property bar" intends no interpretation of "random foo"; it merely claims that the set of foo's with property bar has measure p with respect to some probability measure. In this case, the probability measure is the Bernoulli measure.

http://www.encyclopediaofmath.org/index.php/Bernoulli_measur...

>And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

No, the probability is zero. Which, note, does not mean it's impossible. That's a common misunderstanding of probabilities. E.g., if space is infinitely divisible, then for any particular point on a dartboard, the odds you'll hit that point are 0, and yet this doesn't imply it's impossible to hit the dartboard

Reply on news.ycombinator.com