What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

We can use the Valiant Vazirani Therom, also found here (in more detail).

Essentially, it is a randomized algorithm that converts a SAT formula into another SAT formula that has only 1 satisfying variable assignment (called UNIQUE-SAT) with high probability.

I'm wondering what the upper bounds are on the size of the formula. The information I have proves that it is polynomial, but I hope we can get more specific. Can anyone find a more exact upper bounds?

  • $\begingroup$ @Raphael: I haven't tried much to be honest. It seems to me that we start with a given formula, and can essentially transform it via an $m \times n$ matrix, where $m$ is a guess at $\log_2{\text{(size of new formula)}}$, and $n$ is the size of the original formula. Thus we will have used a linear transformation from the old formula to a new formula. So it seems to me that the new formula size is related to this $(m \times n)$, and thus the new formula size is $O(n \cdot n)$, since $m$ will not exceed $n$ in the worst case. $\endgroup$ – Matt Groff Feb 10 '14 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.