4
$\begingroup$

Unique SAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. I recall reading that P=NP iff Unique SAT is in P (I don't remember where I read it. Notice that Unique SAT is CoNP-hard and Unique SAT= SAT\ Double SAT where Double Sat={$\phi$| $\phi$ has two or more satisfying assignments})

I'm looking for an efficiently computable function $f(s_n)= \phi$ such that formula $\phi$ is uniquely satisfied by assignment $s_n$ where $n$ is the number of variables.

Also, Can $f$ be made a bijection?

Edit 1: Input is a binary string $s_n$, output is a 3SAT formula in CNF.

Basically, I'm looking for an efficient algorithm that computes $f$. Ideally, such algorithm would allows us to construct hard instances for Unique SAT.

EDIT 2: I'm seeking an algorithm that is able to generate all uniquely staisfiable instances not just the easy cases given so far.

$\endgroup$
  • 3
    $\begingroup$ The Valiant-Vazarani theorem shows that NP=RP if Unique-SAT is in P by giving a randomized reduction from SAT, but AFAIK Unique-SAT is not known to be NP-complete leading to the stronger conclusion you mention. $\endgroup$ – Huck Bennett Oct 22 '11 at 18:19
  • 2
    $\begingroup$ @Huck, V-V theorem is about the promise version of Unique SAT. $\endgroup$ – Mohammad Al-Turkistany Oct 22 '11 at 18:23
  • 2
    $\begingroup$ @Huck Valiant-Vazirani theorem talks about complexity class UP not complexity class US. In UP we are promised that there will be either one solution or no solution. In US there is no promise and we accept if there is one solution. $\endgroup$ – Tayfun Pay Oct 22 '11 at 19:19
  • $\begingroup$ @MohammadAl-Turkistany I am having hard time understanding the function f(n). What do you want the input to be and what do you want the output to be. Thanks $\endgroup$ – Tayfun Pay Oct 22 '11 at 19:20
  • 4
    $\begingroup$ I agree that the question is unclear. Suppose for example that $n=3$ and we're given the assignment $(0,0,1)$. Then can't we simply set $\phi = \bar x_1 \wedge \bar x_2 \wedge x_3$? $\endgroup$ – Timothy Chow Oct 22 '11 at 19:47
6
$\begingroup$

If I understand your question correctly, you're looking for ways to generate lots of non-trivial uniquely satisfiable 3SAT instances.

There's a tension between your desire to find a way to generate all uniquely satisfiable instances and your desire to find a way to generate hard uniquely satisfiable instances. For the moment let's ignore your uniqueness condition. Then I know there has been some work on this problem, e.g., see this paper by Achlioptas et al. You might think that they proceed by generating random clauses and discarding the clauses that are inconsistent with a randomly chosen but fixed assignment. But although this method will in principle generate every satisfiable instance (with some probability), it tends to produce instances that are easy to solve. To get hard instances, Achlioptas et al. adopt the approach of picking some known hard problem and generating instances based on that.

I suspect that a similar dilemma will arise for uniquely satisfiable instances. My guess is that a randomized method that generates every uniquely satisfiable instance with some probability will tend to produce easily solved instances. If you want hard instances, your best bet is probably to pick some cryptographic problem (where the unique solution is the cryptographic secret, e.g., a factorization) and generate instances based on that.

$\endgroup$
  • $\begingroup$ Tnanks Timothy for your answer, Are you aware of any effort that studied the density of Unique SAT? $\endgroup$ – Mohammad Al-Turkistany Oct 27 '11 at 9:48
  • $\begingroup$ No, I am not. However, I think you can get a bound from the Valiant-Vazirani argument. They basically show that if you start with any satisfiable instance and add random ${\mathbb F}_2$-linear equations, then with high probability you quickly get a uniquely satisfiable instance. $\endgroup$ – Timothy Chow Oct 27 '11 at 14:31
8
$\begingroup$

I'm not sure that I understand your question. The way I understand it leads to the following construction which is an invertible function from $\{0,1\}^n$ to 3CNFs:

Input: $x \in \{0,1\}^n$ ($x$ is indexed from 0 to $n-1$)

Output: a 3CNF with $\frac{7}{3}n$ clauses (assume 3 divides $n$)

For $0 \leq i < n/3$ pick input variables $x_{3i},x_{3i+1},x_{3i+2}$ and add to the final formula the seven clauses on these three variables which are satisfied by the input.

The output 3CNF is clearly satisfiable only by the assignment. This procedure is well defined for every input and it is invertible. Unfortunately these formulas are easy to recognize, so they are easy to solve.

Another RANDOM process is to add to the formula random clauses among the ones which are not falsified by the given assignment. The formula will stay satisfiable, but no other assignment will satisfy it if you add many generated clauses (I guess $100n$ would be more than enough).

Formulas generated in this way are usually hard to distinguish from purely random 3CNFs with a similar clause/variables ratio (which are unsatisfiable with high probability).

$\endgroup$
  • $\begingroup$ Thanks. Do you have any reference which shows that instances, created according to your second idea, are hard for Unique SAT problem defined in my question? $\endgroup$ – Mohammad Al-Turkistany Oct 24 '11 at 15:13
  • $\begingroup$ Adding only random clauses that do not falsify the hidden assignment produces the planted-SAT distribution, which has been shown to be easily solvable with high probability for clause-to-variable ratios $\Omega$(log n). See Finding a Randomly Planted Assignment in a Random 3-CNF. $\endgroup$ – Kyle Jones Dec 27 '11 at 23:52

Your Answer

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

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