<p>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 <em>isolate</em> a witness, you just need to make their cardinality <em>odd</em>. 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.)</p>

<p>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 <em>unique</em> 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 <em>some</em> randomized poly-time oracle machine $M$ with one-sided error, and <em>some</em> 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.</p>

<p>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}$. </p>

CC BY-SA 3.0
2017-12-07T03:32:42.220Z
If $NP=UP$ then we have $f(n)=1$. So why cannot we conclude $NP=UP\implies NP\subseteq P/poly$  from the DKWM paper? Is there a reason we need something other than $NP=UP$ to show $NP\subseteq P/poly$? $NP=UP$ means there is a deterministic (probability $1$) reduction of $3SAT$ to another $3SAT$ with one solution. We cannot conclude $VV$ success probability is $1$ because the solution of second $SAT$ may not be satisfying in initial problem?
Turbo
CC BY-SA 3.0
2017-12-07T07:02:01.060Z
@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: https://cstheory.stackexchange.com/search?q=npmv
Joshua Grochow
CC BY-SA 3.0
2017-12-07T08:53:25.907Z
Pretty interesting.
Turbo
CC BY-SA 3.0
2017-11-20T17:40:36.410Z
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.
Turbo
CC BY-SA 3.0
2017-11-20T18:04:59.263Z
p=bpp does not imply vv can be derandomized. is there evidence that vv cannot be derandomized implies p is not bpp?
Turbo
CC BY-SA 3.0
2017-11-20T19:28:24.607Z
Re: your first comment, see https://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](http://blog.computationalcomplexity.org/2006/07/full-derandomization.html)). The success prob. of VV can be improved to 2/3 iff $\mathsf{NP} \subseteq \mathsf{P/poly}$ [DKWM](https://eccc.weizmann.ac.il/report/2011/151/).
Joshua Grochow
CC BY-SA 3.0
2017-11-21T04:20:33.553Z
It is interesting that $P=BPP$ does not imply deterministic $VV$ and infact conversely deterministic $VV$ implies $NP$ in $P/poly$ and deterministic $VV$ (contrary to sane beliefs) keeps open the possibility of $NP=RP$ in $P/poly$. Something curiously fishy here.
Turbo
CC BY-SA 3.0
2017-11-21T09:31:19.817Z
Note from what you said $NP\not\subseteq P/poly\implies$ no deterministic $VV\implies E\subseteq SPACE(2^{o(n)})$.
Turbo
CC BY-SA 3.0
2017-11-21T09:47:28.083Z
Which are believed true? (A1). Improving success probability of $VV$ (A2). making $VV$ deterministic (B).$E\subseteq SPACE(2^{o(n)})$? (C). $NP\not\subseteq P/poly$? (D). $P=BPP\implies P^{\oplus P}=BPP^{\oplus P}$ (and so $\oplus P\subseteq P^{\oplus P}\subseteq \oplus P^{\oplus P}\subseteq \oplus P$ gives $P=BPP\implies PH\subseteq \oplus P$).
Turbo
CC BY-SA 3.0
2017-11-21T15:42:50.153Z
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...
Joshua Grochow
CC BY-SA 3.0
2017-11-19T02:05:46.950Z
2017-11-19T02:05:46.950Z
Joshua Grochow
<p>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?</p>

CC BY-SA 3.0
2017-11-17T13:48:08.140Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-11-17T16:10:27.230Z
@SashoNikolov There was a spam there by some escort agency (was strange but I can bring that up). That is why I reposted.
Turbo
CC BY-SA 3.0
2017-11-17T16:31:46.503Z
Pasted up the comment.
Turbo
CC BY-SA 3.0
2017-11-17T16:46:03.913Z
You can just flag such things for moderator attention.
Sasho Nikolov
<cc.complexity-theory><complexity-classes>
Two queries related to Toda
Turbo
# Two queries related to Toda

(Asked by: username_0 on 2017-11-17)

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?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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.  
> **username_0**: @SashoNikolov There was a spam there by some escort agency (was strange but I can bring that up). That is why I reposted.  
> **username_0**: Pasted up the comment.  
> **username_1**: You can just flag such things for moderator attention.  

---

## 1 answers

### Answer by username_2 on 2017-11-19. Score: 4 | Accepted answer

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}$.

> **Comments:**
> **username_0**: 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.  
> **username_0**: p=bpp does not imply vv can be derandomized. is there evidence that vv cannot be derandomized implies p is not bpp?  
> **username_2**: Re: your first comment, see https://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](http://blog.computationalcomplexity.org/2006/07/full-derandomization.html)). The success prob. of VV can be improved to 2/3 iff $\mathsf{NP} \subseteq \mathsf{P/poly}$ [DKWM](https://eccc.weizmann.ac.il/report/2011/151/).  
> **username_0**: It is interesting that $P=BPP$ does not imply deterministic $VV$ and infact conversely deterministic $VV$ implies $NP$ in $P/poly$ and deterministic $VV$ (contrary to sane beliefs) keeps open the possibility of $NP=RP$ in $P/poly$. Something curiously fishy here.  
> **username_0**: Note from what you said $NP\not\subseteq P/poly\implies$ no deterministic $VV\implies E\subseteq SPACE(2^{o(n)})$.  
> **username_0**: Which are believed true? (A1). Improving success probability of $VV$ (A2). making $VV$ deterministic (B).$E\subseteq SPACE(2^{o(n)})$? (C). $NP\not\subseteq P/poly$? (D). $P=BPP\implies P^{\oplus P}=BPP^{\oplus P}$ (and so $\oplus P\subseteq P^{\oplus P}\subseteq \oplus P^{\oplus P}\subseteq \oplus P$ gives $P=BPP\implies PH\subseteq \oplus P$).  
> **username_2**: 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...  
> **username_0**: If $NP=UP$ then we have $f(n)=1$. So why cannot we conclude $NP=UP\implies NP\subseteq P/poly$  from the DKWM paper? Is there a reason we need something other than $NP=UP$ to show $NP\subseteq P/poly$? $NP=UP$ means there is a deterministic (probability $1$) reduction of $3SAT$ to another $3SAT$ with one solution. We cannot conclude $VV$ success probability is $1$ because the solution of second $SAT$ may not be satisfying in initial problem?  
> **username_2**: @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: https://cstheory.stackexchange.com/search?q=npmv  
> **username_0**: Pretty interesting.  

---

