A language is in $\mathsf{Almost\text{-}PSPACE}$ if there is a (deterministic) $\mathsf{PSPACE}$ Turing machine with an oracle $A$ that accepts the language with probability $1$ when the oracle language is chosen uniformly at random [1,2]. (That is, the language accepted by the oracle is determined by tossing a fair coin for each possible string.)

I can't understand the difference between $\mathsf{Almost\text{-}PSPACE}$ and $\mathsf{IPP^A}$.

Is it possible that $\mathsf{P} = \mathsf{PSPACE} \subsetneq \mathsf{Almost\text{-}PSPACE}$? Or, maybe it is already known that $\mathsf{P} \subsetneq \mathsf{Almost\text{-}PSPACE}$? Or it will imply that $\mathsf{P} = \mathsf{Almost\text{-}P} = \mathsf{Almost\text{-}PSPACE}$?

[1] Complexity Zoo.
[2] C.H. Bennett and J. Gill, Relative to a random oracle $A$, $\mathsf{P}\neq\mathsf{NP}\neq\mathsf{co\text{-}NP}$ with probability $1$. SIAM Journal on Computing, 10(1):96–113, 1981. (Paywalled PDF.)

  • $\begingroup$ I'm confused. There isn't a uniform distribution on the set of all languages, is there? $\endgroup$ Commented Jun 5, 2017 at 10:09
  • $\begingroup$ @DavidRicherby, I think it only means that you have equal chances to choose any oracle. For example, chances to choose $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$ are the same. Number of complexity classes is countable, isn't it? I don't know if $\mathsf{A}$ here can be Zeno's Machine, for example. $\endgroup$
    – rus9384
    Commented Jun 5, 2017 at 10:58
  • $\begingroup$ An oracle is for a specific language, and there are uncountably many of those. There's no uniform distribution on the natural numbers, either, so having a countable set of options isn't necessarily helpful. And oracles don't necessarily even have to be for decidable problems. I wonder if there's a better source than Complexity Zoo's vague sketch. $\endgroup$ Commented Jun 5, 2017 at 11:09
  • $\begingroup$ @DavidRicherby, there is a reference to authors of these complexity classes. However, I couldn't look at it. I can't understand if $\mathsf{BP}^{exp} \cdot$ gives more power than $\mathsf{BP} \cdot$ under $\mathsf{P} = \mathsf{PSPACE}$ assumption. $\endgroup$
    – rus9384
    Commented Jun 5, 2017 at 11:47
  • $\begingroup$ @DavidRicherby You use the "coin-toss measure" on $\{0,1\}^{\mathbb{N}}$, a standard construction in measure theory, corresponding to the experiment in which a fair coin is tossed an infinite number of times. Now you just have to check that the event "$L \in \mathsf{PSPACE}^A$" is measurable (in $A$). $\endgroup$ Commented Jun 5, 2017 at 12:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.