<p>The standard meaning of "derandomized Valiant-Vazirani theorem" is the following. </p>

<blockquote>
  <p>There exists a deterministic polynomial time algorithm that, given a 3CNF formula $\phi$, outputs formulas $\psi_1, \ldots, \psi_k$ such that</p>
  
  <ol>
  <li>If $\phi$ is not satisfiable, then none of the $\psi_i$ are.</li>
  <li>If $\phi$ is satisfiable, at least one of the $\psi_i$ has a unique satisfying assignment.</li>
  </ol>
</blockquote>

<p>Indeed, if the above is true, $\mathsf{NP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ (a  comment by Joro suggests that this is what he actually meant). Since $\mathsf{P}^{\oplus \mathsf{P}}$ is closed under complement, it follows that $\mathsf{coNP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ holds as well.</p>

<p>If a derandomized Valiant-Vazirani theorem holds relative to $\oplus P$, i.e. with the 3CNF formulas augmented by $\oplus P$ predicates, then, using Fortnow's argument in his <a href="http://people.cs.uchicago.edu/~fortnow/papers/toda.pdf" rel="nofollow noreferrer">simplified proof</a> of Toda's theorem, we would get $\mathsf{PH} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$. The usual randomized Valiant-Vazirani theorem implies a randomized version of this: $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$. This is one of the lemmas used by Toda.</p>

<p><strong>Note</strong>: My original answer had a bug, thanks to Emil Jeřábek for pointing it out. </p>

CC BY-SA 3.0
2014-07-07T19:48:25.037Z
Does it also imply ${\bf NP} \subseteq {\bf P ^{\bf UP}}$? ... Furthermore, as far as I know, ${\bf \oplus P}$ is closed under Turing reductions so it should be ${\bf NP} \subseteq {\bf \oplus P}$? No? Please let me know if I missed something.
Tayfun Pay
CC BY-SA 3.0
2014-07-07T21:52:30.263Z
@TayfunPay could you provide a reference for the closure of $\oplus \mathsf{P}$ that you are claiming?
Sasho Nikolov
CC BY-SA 3.0
2014-07-07T22:00:03.703Z
The original Paper by Papadimitriou and Zachos where they show that ${\bf \oplus P}= {\bf \oplus P}^{\bf \oplus P}$.. And since when a given class is low for itself, then it is closed under Turing reductions... ${\bf \oplus P}= {\bf  P}^{\bf \oplus P}$. Am I missing something? Ok
Tayfun Pay
CC BY-SA 3.0
2014-07-07T22:48:33.277Z
I guess it is very simple actually, $\mathsf{P}^{\oplus \mathsf{P}} \subseteq \oplus \mathsf{P}^{\oplus \mathsf{P}} = \oplus \mathsf{P}$. Thanks!
Sasho Nikolov
CC BY-SA 3.0
2016-02-21T10:10:32.050Z
@SashoNikolov One of my profs said we cannot derandomize VV theorem. In what sense is this statement true? If $P=BPP$ can we derandomize VV and hence $PH$ is in $P^{\oplus P}$ is a conjecture or am I missing something?
Turbo
CC BY-SA 3.0
2016-02-22T00:46:32.257Z
@Turbo I do not know what your professor meant. I do not think P=BPP itself implies a derandomization of VV. But there are plausible sounding assumptions under which VV can be derandomized, see http://epubs.siam.org/doi/abs/10.1137/S0097539700389652
Sasho Nikolov
CC BY-SA 3.0
2016-02-23T08:13:47.013Z
@SashoNikolov Strange is there a reason why VV derandomization would be eluded by P=BPP?
Turbo
CC BY-SA 3.0
2016-05-02T17:41:56.443Z
@SashoNikolov $\oplus P$ sounds like can be solved by Permanent mod 2 which is det over F_2. Then why is \oplus P not in P?
Turbo
CC BY-SA 3.0
2016-05-05T03:39:36.873Z
@Turbo "sounds like" is not a proof. The reduction from a #P-complete problem to the permanent does not have to preserve parities. For example, the reduction from #3SAT here https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent multiplies the number of satisfying assignments by an even number.
Sasho Nikolov
CC BY-SA 3.0
2017-12-20T08:44:21.203Z
The "easy exercise" does not appear correct. You would need a stronger assumption  $\mathrm{NP^{\oplus P}\subseteq\oplus P}$ for the inductive argument to go through.
Emil Jeřábek
CC BY-SA 3.0
2017-12-21T00:50:32.367Z
@EmilJeřábek It avoids that induction. It replaces randomized Valiant-Vazirani with derandomized version in Toda's approach.
Turbo
CC BY-SA 3.0
2017-12-21T07:28:47.107Z
@EmilJeřábek Thanks, I think I have made a mistake there. It *would* work (in the same way as in Fortnow's paper) if a "derandomized Valiant-Vazirani" theorem were true with an oracle for $\oplus P$.
Sasho Nikolov
CC BY-SA 3.0
2014-07-07T14:12:55.157Z
2017-12-21T07:37:19.953Z
2017-12-21T07:37:19.953Z
Sasho Nikolov
<p>The Unambiguous SAT problem (USAT) is to determine whether a 
given formula has a satisfying assignment, when we are 
guaranteed that it has at most one satisfying assignment.</p>

<p>By a theorem Valiant-Vazirani there is probabilistic
reduction from 3SAT to USAT. Given 3SAT formula $\phi$,
over $n$ variables, the algorithm produces $n+2$ formulas
$\phi_i$ with the properties:  if $\phi$ is UNSAT, all $\phi_i$
are UNSAT. Otherwise the probability that $\phi_i$ has exactly
one solution is $\ge \frac18$.</p>

<p>$\oplus P$ is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd.</p>

<p>Since USAT has zero or one solution, $\oplus P$ solves USAT.</p>

<blockquote>
  <p>Would derandomizing the reduction SAT to USAT imply $NP$ and $coNP$ are in  $\oplus P$?</p>
</blockquote>

<p>This looks plausible to me, though <a href="https://en.wikipedia.org/wiki/Parity_P" rel="nofollow noreferrer">Wikipedia</a> claims 
"there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME" and $P^{\oplus P}$ is not known to even contain $NP$.</p>

<p>Even it can't be derandomized the reduction to USAT appears
very good in practice given $\oplus P$ oracle.</p>

CC BY-SA 3.0
2014-07-06T19:28:11.723Z
Unique-SAT is US-Complete. The problem in question is Unambiguous-SAT, which is a promise problem for complexity class UP.
Tayfun Pay
CC BY-SA 3.0
2014-07-06T20:06:09.370Z
If by a derandomization you mean a deterministic polytime algorithm that maps a 3CNF $\phi$ to a list of 3CNFS $\psi_1, \ldots, \psi_k$, such that if $\phi$ is unsatisfiable, than all $\psi_i$ are unsatisfiable, and if $\phi$ is satisfiable, at least one of the $\psi_i$ has a unique satisfying solution, then I see how this would imply that $\mathsf{NP}$ and $\mathsf{coNP}$ are in $\mathsf{P}^{\oplus \mathsf{P}}$. However, to show containment in $\oplus\mathsf{P}$, you need this class to be closed under unions, and I don't think that's known.
Sasho Nikolov
CC BY-SA 3.0
2014-07-07T13:09:32.477Z
@SashoNikolov Basically I meant if I had parity P oracle in practice I will solve SAT with high probability (this is not deterministic). Your proposed reduction is very close to [this paper p. 15 Thm 5.2](https://www.cs.utexas.edu/~klivans/amjourn.ps)
joro
<cc.complexity-theory><sat>
Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$?
joro
# Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$?

(Asked by: username_0 on 2014-07-06)

The Unambiguous SAT problem (USAT) is to determine whether a
given formula has a satisfying assignment, when we are
guaranteed that it has at most one satisfying assignment.

By a theorem Valiant-Vazirani there is probabilistic
reduction from 3SAT to USAT. Given 3SAT formula $\phi$,
over $n$ variables, the algorithm produces $n+2$ formulas
$\phi\_i$ with the properties: if $\phi$ is UNSAT, all $\phi\_i$
are UNSAT. Otherwise the probability that $\phi\_i$ has exactly
one solution is $\ge \frac18$.

$\oplus P$ is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd.

Since USAT has zero or one solution, $\oplus P$ solves USAT.

> Would derandomizing the reduction SAT to USAT imply $NP$ and $coNP$ are in $\oplus P$?

This looks plausible to me, though [Wikipedia](https://en.wikipedia.org/wiki/Parity_P) claims
"there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME" and $P^{\oplus P}$ is not known to even contain $NP$.

Even it can't be derandomized the reduction to USAT appears
very good in practice given $\oplus P$ oracle.

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: Unique-SAT is US-Complete. The problem in question is Unambiguous-SAT, which is a promise problem for complexity class UP.  
> **username_2**: If by a derandomization you mean a deterministic polytime algorithm that maps a 3CNF $\phi$ to a list of 3CNFS $\psi_1, \ldots, \psi_k$, such that if $\phi$ is unsatisfiable, than all $\psi_i$ are unsatisfiable, and if $\phi$ is satisfiable, at least one of the $\psi_i$ has a unique satisfying solution, then I see how this would imply that $\mathsf{NP}$ and $\mathsf{coNP}$ are in $\mathsf{P}^{\oplus \mathsf{P}}$. However, to show containment in $\oplus\mathsf{P}$, you need this class to be closed under unions, and I don't think that's known.  
> **username_0**: @SashoNikolov Basically I meant if I had parity P oracle in practice I will solve SAT with high probability (this is not deterministic). Your proposed reduction is very close to [this paper p. 15 Thm 5.2](https://www.cs.utexas.edu/~klivans/amjourn.ps)  

---

## 1 answers

### Answer by username_2 on 2014-07-07. Score: 6

The standard meaning of "derandomized Valiant-Vazirani theorem" is the following.

> There exists a deterministic polynomial time algorithm that, given a 3CNF formula $\phi$, outputs formulas $\psi\_1, \ldots, \psi\_k$ such that
>
> 1. If $\phi$ is not satisfiable, then none of the $\psi\_i$ are.
> 2. If $\phi$ is satisfiable, at least one of the $\psi\_i$ has a unique satisfying assignment.

Indeed, if the above is true, $\mathsf{NP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ (a comment by Joro suggests that this is what he actually meant). Since $\mathsf{P}^{\oplus \mathsf{P}}$ is closed under complement, it follows that $\mathsf{coNP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ holds as well.

If a derandomized Valiant-Vazirani theorem holds relative to $\oplus P$, i.e. with the 3CNF formulas augmented by $\oplus P$ predicates, then, using Fortnow's argument in his [simplified proof](http://people.cs.uchicago.edu/~fortnow/papers/toda.pdf) of Toda's theorem, we would get $\mathsf{PH} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$. The usual randomized Valiant-Vazirani theorem implies a randomized version of this: $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$. This is one of the lemmas used by Toda.

**Note**: My original answer had a bug, thanks to username_4 for pointing it out.

> **Comments:**
> **username_1**: Does it also imply ${\bf NP} \subseteq {\bf P ^{\bf UP}}$? ... Furthermore, as far as I know, ${\bf \oplus P}$ is closed under Turing reductions so it should be ${\bf NP} \subseteq {\bf \oplus P}$? No? Please let me know if I missed something.  
> **username_2**: @TayfunPay could you provide a reference for the closure of $\oplus \mathsf{P}$ that you are claiming?  
> **username_1**: The original Paper by Papadimitriou and Zachos where they show that ${\bf \oplus P}= {\bf \oplus P}^{\bf \oplus P}$.. And since when a given class is low for itself, then it is closed under Turing reductions... ${\bf \oplus P}= {\bf  P}^{\bf \oplus P}$. Am I missing something? Ok  
> **username_2**: I guess it is very simple actually, $\mathsf{P}^{\oplus \mathsf{P}} \subseteq \oplus \mathsf{P}^{\oplus \mathsf{P}} = \oplus \mathsf{P}$. Thanks!  
> **username_3**: @SashoNikolov One of my profs said we cannot derandomize VV theorem. In what sense is this statement true? If $P=BPP$ can we derandomize VV and hence $PH$ is in $P^{\oplus P}$ is a conjecture or am I missing something?  
> **username_2**: @username_3 I do not know what your professor meant. I do not think P=BPP itself implies a derandomization of VV. But there are plausible sounding assumptions under which VV can be derandomized, see http://epubs.siam.org/doi/abs/10.1137/S0097539700389652  
> **username_3**: @SashoNikolov Strange is there a reason why VV derandomization would be eluded by P=BPP?  
> **username_3**: @SashoNikolov $\oplus P$ sounds like can be solved by Permanent mod 2 which is det over F_2. Then why is \oplus P not in P?  
> **username_2**: @username_3 "sounds like" is not a proof. The reduction from a #P-complete problem to the permanent does not have to preserve parities. For example, the reduction from #3SAT here https://en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent multiplies the number of satisfying assignments by an even number.  
> **username_4**: The "easy exercise" does not appear correct. You would need a stronger assumption  $\mathrm{NP^{\oplus P}\subseteq\oplus P}$ for the inductive argument to go through.  
> **username_3**: @EmilJeřábek It avoids that induction. It replaces randomized Valiant-Vazirani with derandomized version in Toda's approach.  
> **username_2**: @EmilJeřábek Thanks, I think I have made a mistake there. It *would* work (in the same way as in Fortnow's paper) if a "derandomized Valiant-Vazirani" theorem were true with an oracle for $\oplus P$.  

---

