2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Unique-SAT is US-Complete. The problem in question is Unambiguous-SAT, which is a promise problem for complexity class UP. $\endgroup$
    – Tayfun Pay
    Jul 6, 2014 at 19:28
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jul 6, 2014 at 20:06
  • $\begingroup$ @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 $\endgroup$
    – joro
    Jul 7, 2014 at 13:09

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – Tayfun Pay
    Jul 7, 2014 at 19:48
  • $\begingroup$ @TayfunPay could you provide a reference for the closure of $\oplus \mathsf{P}$ that you are claiming? $\endgroup$
    – Sasho Nikolov
    Jul 7, 2014 at 21:52
  • 2
    $\begingroup$ 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 $\endgroup$
    – Tayfun Pay
    Jul 7, 2014 at 22:00
  • 1
    $\begingroup$ @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 $\endgroup$
    – Sasho Nikolov
    Feb 22, 2016 at 0:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    May 5, 2016 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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