Is the Isolation lemma crucial for $PH\subseteq BPP^{\oplus P}$ theorem and would avoiding the Isolation lemma say anything more that is not known?

  • 5
    $\begingroup$ There was a very similar previous question by you, with some interesting comments, which you have now deleted for some reason. I find this annoying. $\endgroup$ – Sasho Nikolov Nov 17 '17 at 13:48
  • $\begingroup$ @SashoNikolov There was a spam there by some escort agency (was strange but I can bring that up). That is why I reposted. $\endgroup$ – 1.. Nov 17 '17 at 16:10
  • $\begingroup$ Pasted up the comment. $\endgroup$ – 1.. Nov 17 '17 at 16:31
  • 8
    $\begingroup$ You can just flag such things for moderator attention. $\endgroup$ – Sasho Nikolov Nov 17 '17 at 16:46

Re 1: It seems unlikely to me that the Isolation Lemma is necessary for $\mathsf{PH} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$. For example, even for $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ you don't need to isolate a witness, you just need to make their cardinality odd. That being said, I think the only known proof of $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ goes through Valiant-Vazirani. (But proving that Valiant-Vazirani is necessary for $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ - that is, that $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}} \Rightarrow \mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ - also seems hard, if not false.)

Now, if you ask if the isolation lemma is necessary for the Valiant-Vazirani Theorem ($\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$), this seems more plausible - since you're reducing from many witnesses to a unique witness - but still hard to prove. To actually prove this, you'd want to prove that just based on the assumption $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ that you get some version of an isolation lemma. The reason I say this seems hard to prove is as follows. Suppose you wanted to prove this. Then you'd take, say, SAT and try to show that you can isolate witnesses. The issue is that all you know from the assumption is that there is some randomized poly-time oracle machine $M$ with one-sided error, and some oracle in $\mathcal{O} \in \mathsf{PromiseUP}$ such that $SAT = L(M^\mathcal{O})$. But nothing in this assumption says that the witnesses for the $\mathcal{O}$ oracle are in any way related to the satisfying assignments for SAT (other than that $SAT = L(M^\mathcal{O})$). Even if you could somehow show such a relationship, you still don't know that the machine $M$ produces oracle queries such that the witnesses for those queries are related to the witnesses to the original SAT assignments. Nonetheless, philosophically it at least seems plausible to me that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ is equivalent to the isolation lemma.

The question of whether the isolation lemma is necessary for the Valiant-Vazirani Theorem - and the issue I raised in the preceding paragraph - are closely related to the difference between, say, $\mathsf{NP} = \mathsf{UP}$ and $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$. The latter essentially says that you can indeed isolate witnesses, at least nondeterministically. I suppose the isolation lemma itself can be formalized in terms of complexity classes as $\mathsf{NPMV} \subseteq_c \mathsf{RPSV}$.

| cite | improve this answer | |
  • $\begingroup$ i looked at npmv and npsv in the zoo. they seem to be functional problems and npsv always O/Ps same value while npmv can O/P different values. I do not know what functions mean here for accepting paths. I dont see the connection to up and np and indeed the need for isolation lemma. $\endgroup$ – 1.. Nov 20 '17 at 17:40
  • $\begingroup$ p=bpp does not imply vv can be derandomized. is there evidence that vv cannot be derandomized implies p is not bpp? $\endgroup$ – 1.. Nov 20 '17 at 18:04
  • 1
    $\begingroup$ Re: your first comment, see cstheory.stackexchange.com/a/19761/129. The basic connection is: given a verifier $V(x,w)$ (defining the NP language $L = \{x : \exists^p w V(x,w)=1\}$), consider the NPMV machine that on input $x$ outputs all $w$ such that $V(x,w)=1$. If VV can not be derandomized then $\mathsf{E} \subseteq \mathsf{SPACE}(2^{o(n)})$ (see, e.g., here). The success prob. of VV can be improved to 2/3 iff $\mathsf{NP} \subseteq \mathsf{P/poly}$ DKWM. $\endgroup$ – Joshua Grochow Nov 20 '17 at 19:28
  • 1
    $\begingroup$ You have to read the DKWM paper carefully. Deterministic VV is not the same as improving the success probability to 1. The success probability has to do with the number of formulae output by the reduction such that one of them has a unique witness w.h.p. Whether there is a deterministic reduction that outputs $f(n)$ formulae for any given $f$ is a separate question. Derandomization implies the latter for $f(n)=O(n)$. DKWM talk about the (im)possibility of getting $f(n)=O(1)$. I think A2 and C are believed; D might be "trivially" true because both its antecedent and consequent are true... $\endgroup$ – Joshua Grochow Nov 21 '17 at 15:42
  • 1
    $\begingroup$ @Turbo: NP=UP does not imply $f(n)=1$; you need $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ for the argument you are trying to make work, not just NP=UP. The issue with only assuming NP=UP is that the witnesses for the UP machine can be totally unrelated to those for the NP machine, but the standard notion of "isolation" considered in DKWM is that you are selecting one witness from among the witnesses for the given NP machine. For more on this distinction see, e.g., these: cstheory.stackexchange.com/search?q=npmv $\endgroup$ – Joshua Grochow Dec 7 '17 at 7:02

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.