<p>No, but I don't know what would count as a proof. People conjecture P=BPP and IP<span class="math-container">$\ne$</span>NP, if that is good enough.</p>

CC BY-SA 4.0
2019-11-19T17:13:01.203Z
Thanks domotorp. But, I want more details. For example, why not? In claim 1, he states that without randomness and with interaction, the model equals NP.
user777
CC BY-SA 4.0
2019-11-19T17:09:56.990Z
2019-11-19T17:09:56.990Z
domotorp
<p>This is not known, but as domotorp stated, it is believed not to be the case. First, note that <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> doesn't say that randomness isn't useful in <em>any</em> context, just in the context of poly-time decision problems. For example, just assuming <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> is already not known to imply that <span class="math-container">$\mathsf{AM} = \mathsf{NP}$</span> (and the latter is even weaker than <span class="math-container">$\mathsf{IP} = \mathsf{NP}$</span>). To give you a little intuition, the point is this: <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> says that when deciding a <em>deterministic</em> thing, randomness doesn't help (up to poly factors). But in interactive proofs, the randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover. </p>

<p>As a related (but admittedly different) example note that even if <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span>, that doesn't obviate the need for randomness in distributed computing. For example, selecting unique IDs for processors in a distributed system can be done using randomness with high probability (everyone just picks a random ID from a large enough range), and even if <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> there seems to be essentially no way to remove this use of randomness. (Same goes for one-time pads in crypto.)</p>

<p>I suppose some more formal evidence would be an oracle relative to which <span class="math-container">$\mathsf{P} = \mathsf{BPP}$</span> and yet <span class="math-container">$\mathsf{IP} \neq \mathsf{NP}$</span> - shouldn't be too hard to construct...</p>

CC BY-SA 4.0
2019-11-19T18:14:22.077Z
Thank you Joshua. I thought that BPP = P, means 'randomness' is useless in general and we can derandomize every single randomized algorithm up to polynomial time. It is nice answer at least to know that randomness in IP is different from randomness in world of deterministic, but given an oracle to show that $P = BPP$ and $IP  \neq NP$ would be nice result.
user777
CC BY-SA 4.0
2019-11-20T09:54:19.440Z
"randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover." is the prover deterministic?
VS.
CC BY-SA 4.0
2019-11-20T16:21:37.937Z
@VS.The prover is allowed to be nondeterministic: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ip
Joshua Grochow
CC BY-SA 4.0
2019-11-19T17:32:09.927Z
2019-11-19T17:32:09.927Z
Joshua Grochow
<p>This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, this is not a repeated question, my question is the following:</p>

<p>I'm now studying Interactive Proof System in Goldreich's textbook and <a href="http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec10.pdf" rel="nofollow noreferrer">here</a>. I have the following question:</p>

<p>Suppose P=BPP, then this show that randomness doesn't give us power over deterministic model (moreover, this would show that we can derandomize every randomness algorithm into deterministic model). Now, In interactive proof system, we know that if Verifier is deterministic, then Prover can guess all questions that Verifier would ask. So, interactive proof system is useless without randomness (see Claim 1 in the above lecture note). Moreover, interactive proof system such that Verifier is not using randomness would be equivalent to class NP. Now, does this mean if P=BPP, then IP=NP? Why I say something like that? Well, since Prover has unbounded computation power, then Prover can simulate randomness by derandomness.</p>

<p>Thank you!</p>

CC BY-SA 4.0
2019-11-19T17:32:03.067Z
Isn't the short answer that, as far as we know, randomness may not be very helpful (i.e. lead to superpoly speedups) in non-interactive computation, but may still be helpful in interactive computation?
Sasho Nikolov
CC BY-SA 4.0
2019-11-19T17:35:44.453Z
@SashoNikolov I think the OP asks for a statement or conjecture that supports view that only in interactive computation randomness helps.
VS.
CC BY-SA 4.0
2019-11-19T17:40:20.080Z
@VS. really? I thought he was asking for an explanation where his reasoning goes wrong. But as far as conjectures, P=BPP assuming plausible circuit lower bounds, while BPP = IP and BPP = P would imply P = PSPACE, which sounds wildly implausible to me.
Sasho Nikolov
CC BY-SA 4.0
2019-11-19T17:43:29.373Z
Well he gives a possibility of P=BPP and IP=NP with implicit possibility of P not NP. So I think then he is asking something else.
VS.
CC BY-SA 4.0
2019-11-19T22:04:40.033Z
As a quick sanity check, it's still unknown if P = NP entails P = PSPACE. If the above result were known, then we'd have the simple result (P = NP) -> (P = PH) -> (P = BPP) -> (NP = IP) -> (P = PSPACE).
Yonatan N
<derandomization><interactive-proofs>
If $P=BPP$, then Is it correct that $IP=NP$?
user777
# If $P=BPP$, then Is it correct that $IP=NP$?

(Asked by: username_0 on 2019-11-19)

This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, this is not a repeated question, my question is the following:

I'm now studying Interactive Proof System in Goldreich's textbook and [here](http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec10.pdf). I have the following question:

Suppose P=BPP, then this show that randomness doesn't give us power over deterministic model (moreover, this would show that we can derandomize every randomness algorithm into deterministic model). Now, In interactive proof system, we know that if Verifier is deterministic, then Prover can guess all questions that Verifier would ask. So, interactive proof system is useless without randomness (see Claim 1 in the above lecture note). Moreover, interactive proof system such that Verifier is not using randomness would be equivalent to class NP. Now, does this mean if P=BPP, then IP=NP? Why I say something like that? Well, since Prover has unbounded computation power, then Prover can simulate randomness by derandomness.

Thank you!

**Tags:** derandomization, interactive-proofs

> **Comments:**
> **username_1**: Isn't the short answer that, as far as we know, randomness may not be very helpful (i.e. lead to superpoly speedups) in non-interactive computation, but may still be helpful in interactive computation?  
> **username_2**: @SashoNikolov I think the OP asks for a statement or conjecture that supports view that only in interactive computation randomness helps.  
> **username_1**: @username_2 really? I thought he was asking for an explanation where his reasoning goes wrong. But as far as conjectures, P=BPP assuming plausible circuit lower bounds, while BPP = IP and BPP = P would imply P = PSPACE, which sounds wildly implausible to me.  
> **username_2**: Well he gives a possibility of P=BPP and IP=NP with implicit possibility of P not NP. So I think then he is asking something else.  
> **username_3**: As a quick sanity check, it's still unknown if P = NP entails P = PSPACE. If the above result were known, then we'd have the simple result (P = NP) -> (P = PH) -> (P = BPP) -> (NP = IP) -> (P = PSPACE).  

---

## 2 answers

### Answer by username_5 on 2019-11-19. Score: 10 | Accepted answer

This is not known, but as username_4 stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in *any* context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the latter is even weaker than $\mathsf{IP} = \mathsf{NP}$). To give you a little intuition, the point is this: $\mathsf{P} = \mathsf{BPP}$ says that when deciding a *deterministic* thing, randomness doesn't help (up to poly factors). But in interactive proofs, the randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover.

As a related (but admittedly different) example note that even if $\mathsf{P} = \mathsf{BPP}$, that doesn't obviate the need for randomness in distributed computing. For example, selecting unique IDs for processors in a distributed system can be done using randomness with high probability (everyone just picks a random ID from a large enough range), and even if $\mathsf{P} = \mathsf{BPP}$ there seems to be essentially no way to remove this use of randomness. (Same goes for one-time pads in crypto.)

I suppose some more formal evidence would be an oracle relative to which $\mathsf{P} = \mathsf{BPP}$ and yet $\mathsf{IP} \neq \mathsf{NP}$ - shouldn't be too hard to construct...

> **Comments:**
> **username_0**: Thank you Joshua. I thought that BPP = P, means 'randomness' is useless in general and we can derandomize every single randomized algorithm up to polynomial time. It is nice answer at least to know that randomness in IP is different from randomness in world of deterministic, but given an oracle to show that $P = BPP$ and $IP  \neq NP$ would be nice result.  
> **username_2**: "randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover." is the prover deterministic?  
> **username_5**: @username_2The prover is allowed to be nondeterministic: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ip  

---

### Answer by username_4 on 2019-11-19. Score: 2

No, but I don't know what would count as a proof. People conjecture P=BPP and IP$\ne$NP, if that is good enough.

> **Comments:**
> **username_0**: Thanks username_4. But, I want more details. For example, why not? In claim 1, he states that without randomness and with interaction, the model equals NP.  

---

