<p>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:</p>

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

<p><strong>Output</strong>: a 3CNF with $\frac{7}{3}n$ clauses (assume 3 divides $n$)</p>

<p>For $0 \leq i &lt; 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.</p>

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

<p>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).</p>

<p>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).</p>

CC BY-SA 3.0
2011-10-24T15:13:06.593Z
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?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-12-27T23:52:14.133Z
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](http://www.cs.technion.ac.il/~eli/papers/planted03.ps).
Kyle Jones
CC BY-SA 3.0
2011-10-23T18:41:43.350Z
2011-10-23T18:41:43.350Z
MassimoLauria
<p>If I understand your question correctly, you're looking for ways to <i>generate</i> lots of non-trivial uniquely satisfiable 3SAT instances.</p>
<p>There's a tension between your desire to find a way to generate <i>all</i> uniquely satisfiable instances and your desire to find a way to generate <i>hard</i> 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 <a href="http://www.cs.cornell.edu/gomes/pdf/2000_achlioptas_aaai_iaai_satisfiable.pdf" rel="nofollow noreferrer">Generating satisfiable problem instances</a> 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.</p>
<p>I suspect that a similar dilemma will arise for <i>uniquely</i> 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.</p>

CC BY-SA 3.0
2011-10-27T09:48:44.830Z
Tnanks Timothy for your answer, Are you aware of any effort that studied the density of Unique SAT?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-27T14:31:08.260Z
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.
Timothy Chow
CC BY-SA 4.0
2011-10-26T22:03:28.170Z
2020-11-25T15:09:53.557Z
2020-11-25T15:09:53.557Z
Timothy Chow
<p>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}) </p>

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

<p>Also, Can $f$ be made a bijection?   </p>

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

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

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

CC BY-SA 3.0
2011-10-22T18:19:04.830Z
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.
Huck Bennett
CC BY-SA 3.0
2011-10-22T18:23:36.583Z
@Huck, V-V theorem is about the promise version of Unique  SAT.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-22T19:19:51.980Z
@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.
Tayfun Pay
CC BY-SA 3.0
2011-10-22T19:20:52.303Z
@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
Tayfun Pay
CC BY-SA 3.0
2011-10-22T19:47:47.030Z
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$?
Timothy Chow
CC BY-SA 3.0
2011-10-22T20:06:13.453Z
@TimothyChow, assume that the number of 3SAT clauses is $\omega(n)$ where n is the number of variables
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-23T00:55:50.610Z
Can't you then take any large enough formula that is satisfied by the given assignment and add the clauses as @TimothyChow suggests?
Sasho Nikolov
CC BY-SA 3.0
2011-10-23T09:05:04.593Z
@Sasho, I'm not interested in trivial instances of uniquely satisfiable formulas.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-23T10:52:02.483Z
that's exactly the point! your definition of $f$ doesn't exclude trivial formulas. so as it stands, $f$ is either uninteresting or not well defined.
Sasho Nikolov
CC BY-SA 3.0
2011-10-23T12:37:33.437Z
@Sasho, I stated that output is in 3SAT CNF where each clause contains three distinct variables.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-23T19:54:29.893Z
that's an issue that's pretty easy to fix, c.f. massimo's first construction
Sasho Nikolov
CC BY-SA 3.0
2011-10-25T11:35:00.453Z
@TimothyChow, I'm seeking an algorithm that is able to generate all uniquely staisfiable instances not just the easy cases that you mentioned.
Mohammad Al-Turkistany
<cc.complexity-theory><unique-solution>
Constructing uniquely satisfiable formulas
Mohammad Al-Turkistany
# Constructing uniquely satisfiable formulas

(Asked by: username_0 on 2011-10-22)

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.

**Tags:** cc.complexity-theory, unique-solution

> **Comments:**
> **username_1**: 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.  
> **username_0**: @Huck, V-V theorem is about the promise version of Unique  SAT.  
> **username_2**: @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.  
> **username_2**: @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  
> **username_3**: 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$?  
> **username_0**: @TimothyChow, assume that the number of 3SAT clauses is $\omega(n)$ where n is the number of variables  
> **username_4**: Can't you then take any large enough formula that is satisfied by the given assignment and add the clauses as @TimothyChow suggests?  
> **username_0**: @Sasho, I'm not interested in trivial instances of uniquely satisfiable formulas.  
> **username_4**: that's exactly the point! your definition of $f$ doesn't exclude trivial formulas. so as it stands, $f$ is either uninteresting or not well defined.  
> **username_0**: @Sasho, I stated that output is in 3SAT CNF where each clause contains three distinct variables.  
> **username_4**: that's an issue that's pretty easy to fix, c.f. massimo's first construction  
> **username_0**: @TimothyChow, I'm seeking an algorithm that is able to generate all uniquely staisfiable instances not just the easy cases that you mentioned.  

---

## 2 answers

### Answer by username_3 on 2011-10-26. Score: 10 | Accepted answer

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](http://www.cs.cornell.edu/gomes/pdf/2000_achlioptas_aaai_iaai_satisfiable.pdf) 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.

> **Comments:**
> **username_0**: Tnanks Timothy for your answer, Are you aware of any effort that studied the density of Unique SAT?  
> **username_3**: 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.  

---

### Answer by username_5 on 2011-10-23. Score: 8

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

> **Comments:**
> **username_0**: 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?  
> **username_6**: 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](http://www.cs.technion.ac.il/~eli/papers/planted03.ps).  

---

