9
$\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.

Improve this question
$\endgroup$
12
  • 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, 2011 at 18:19
  • 2
    $\begingroup$ @Huck, V-V theorem is about the promise version of Unique SAT. $\endgroup$
    – Mohammad Al-Turkistany
    Oct 22, 2011 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, 2011 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, 2011 at 19:20
  • 5
    $\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, 2011 at 19:47

2 Answers 2

Reset to default
10
$\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 Generating satisfiable problem instances by Achlioptas, Gomes, Kautz, and Selman. 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.

Improve this answer
$\endgroup$
2
  • $\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, 2011 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, 2011 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).

Improve this answer
$\endgroup$
2
  • $\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, 2011 at 15:13
  • 1
    $\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, 2011 at 23:52

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.