8 votes
Accepted

Is $UP\not=NP$ with respect to random oracle?

Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity ...
Joshua Grochow's user avatar
8 votes
Accepted

Almost-P and related definitions

The question seems to be predicated on a misunderstanding: the statements “relative to a random oracle $A$, $\mathrm{P}^A=\mathrm{BPP}^A$” and “$\mathrm{Almost\text-P}=\mathrm{BPP}$” are not meant to ...
Emil Jeřábek's user avatar
7 votes
Accepted

What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '...
Joshua Grochow's user avatar
2 votes

Is true randomness and the physical Church-Turing thesis incompatible?

The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random ...
Thomas Klimpel's user avatar
1 vote

Is true randomness and the physical Church-Turing thesis incompatible?

In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable ...
Bjørn Kjos-Hanssen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible