# Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus 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.

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

• Unique-SAT is US-Complete. The problem in question is Unambiguous-SAT, which is a promise problem for complexity class UP. – Tayfun Pay Jul 6 '14 at 19:28
• 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 Jul 6 '14 at 20:06
• @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 – joro Jul 7 '14 at 13:09

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 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 Emil Jeřábek for pointing it out.

• 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 Jul 7 '14 at 19:48
• @TayfunPay could you provide a reference for the closure of $\oplus \mathsf{P}$ that you are claiming? – Sasho Nikolov Jul 7 '14 at 21:52
• 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 Jul 7 '14 at 22:00
• @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 epubs.siam.org/doi/abs/10.1137/S0097539700389652 – Sasho Nikolov Feb 22 '16 at 0:46
• @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 en.wikipedia.org/wiki/Sharp-P-completeness_of_01-permanent multiplies the number of satisfying assignments by an even number. – Sasho Nikolov May 5 '16 at 3:39