2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Nov 19 at 17:32
  • $\begingroup$ @SashoNikolov I think the OP asks for a statement or conjecture that supports view that only in interactive computation randomness helps. $\endgroup$ – VS. Nov 19 at 17:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Nov 19 at 17:40
  • $\begingroup$ 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. $\endgroup$ – VS. Nov 19 at 17:43
  • 3
    $\begingroup$ 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). $\endgroup$ – Yonatan N Nov 19 at 22:04
11
$\begingroup$

This is not known, but as domotorp 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...

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user777 Nov 19 at 18:14
  • $\begingroup$ "randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover." is the prover deterministic? $\endgroup$ – VS. Nov 20 at 9:54
  • $\begingroup$ @VS.The prover is allowed to be nondeterministic: complexityzoo.uwaterloo.ca/Complexity_Zoo:I#ip $\endgroup$ – Joshua Grochow Nov 20 at 16:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user777 Nov 19 at 17:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.