2
$\begingroup$

As I was browsing the Complexity Zoo, I came across this statement:

Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86].

What confused me was the addition of "with probability 1". What does that mean and why is the current formulation different from

Relative to a random oracle, PH is strictly contained in PSPACE [Cai86].

A related question: is there a difference between saying something is deterministic or some process succeeds with probability one?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The latter would imply that the statement holds for every random oracle; the former statement only asserts it is true for "most" random oracles, with some vanishingly small fraction that don't satisfy the claim.

For example: "a randomly chosen integer is non-zero with probability 1" is true, because the odds of picking 0 from all infinitely many integers is 0. But "a randomly chosen integer is non-zero" is false, because we could pick 0.

Edit: as pointed out in the comments, a correct example distribution would instead be a uniform distribution over $[0,1]$. A number selected from this distribution is non-zero with probability 1, but not all numbers in this distribution are non-zero.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I can't make sense of the example. There is no probability measure on the integers such that every individual number has probability 0. What makes it possible in the result in question that "probability 1" does not mean "all" is that the space of all oracles is uncountable. $\endgroup$
    – Emil Jeřábek
    Jul 7 at 13:03
  • 1
    $\begingroup$ @EmilJeřábek Just switch his example to uniform distribution on $[0,1] \subseteq \mathbb{R}$. $\endgroup$
    – mathworker21
    Jul 7 at 13:15
  • 1
    $\begingroup$ Though there are distributions on the integers where 0 has probability 0, so uncountability is not required. :) $\endgroup$
    – Geoffrey Irving
    Jul 7 at 13:40
  • 1
    $\begingroup$ @GeoffreyIrving Yes, I was being sloppy. I should have written "all elements of support". $\endgroup$
    – Emil Jeřábek
    Jul 7 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.