1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ I'm confused. There isn't a uniform distribution on the set of all languages, is there? $\endgroup$ – David Richerby Jun 5 '17 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 Jun 5 '17 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$ – David Richerby Jun 5 '17 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 Jun 5 '17 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$ – Yuval Filmus Jun 5 '17 at 12:14

Your Answer

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

Browse other questions tagged or ask your own question.