What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Tag Info

16

Yes. First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood ...

10

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from Toda-Ogihara

9

(I am interpreting this question in the following way due to the comments.) In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings. This situation is troublesome for formal analyses (reductions) of these systems because, when ...

8

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 Zoo for questions like this...

8

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 be rephrasings of each other. The complexity zoo refers to a paper of Bennett and Gill, which proves the former statement (and many other things) in detail, but ...

7

While the order of quantifiers between what you are asking and almost P differ, it is not too hard to show that they are equivalent. First, for any fixed L, the question of whether L \in P^O does not depend on any finite initial segment of O. it follows that the probability that L \in P^R is either 0 or 1. From the almost -P result, for each computable ...

7

$\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 '98. (freely available author's version)

2

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 output (for a given input)? There is at most one (random) output occurring with probability $>\frac{1}{2}$, so taking that output if it exists (and undefined ...

1

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 sequence. So Church-Turing and true randomness would seem to be incompatible. There is a deeper problem with "true randomness", though: what does it even mean ...

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