Polynomial-Time Hierarchy Is Infinite Under a Random Oracle

http://blog.computationalcomplexity.org/2015/04/ph-infinite-under-random-oracle.html

by 2510c39011c5 • 11 years ago

34 11 11 years ago

blog.computationalcomplexity.org

skissane2• 11 years ago

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?

YokoZar• 11 years ago

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

skissane2• 11 years ago

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

anonetal• 11 years ago

"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).

joe_the_user• 11 years ago

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...

Retra• 11 years ago

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.

ultrafilter• 11 years ago

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...

xamuel• 11 years ago

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

_asummers• 11 years 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.

Polynomial-Time Hierarchy Is Infinite Under a Random Oracle

Related Stories