<p>The decision problem Unique SAT ={<span class="math-container">$\phi$</span>  has unique satisfying assignment } represents a class of computational problems. P=NP iff Unique SAT is in P. Notice that Unique SAT is CoNP-hard and Unique SAT= SAT\ Double SAT ( Double SAT={<span class="math-container">$\phi$</span> has at least two satisfying assignments }).</p>
<p>Considering the search problem of finding the assignment that satisfies a uniquely satisfiable 3SAT formula (i.e. the promise is that  the input formula is uniquely satisfiable).  The best known algorithm is exponential. Unique 3-SAT can be solved in time <span class="math-container">$O(1.307^n)$</span> using a variation of PPSZ algorithm.</p>
<blockquote>
<p>Does an efficient algorithm for the search problem ( with Uniquness prommise) imply efficient deterministic algorithm for the decision problem Unique SAT?</p>
</blockquote>

CC BY-SA 4.0
2022-07-03T14:49:45.997Z
Such a procedure would imply $NP\subseteq BPP$ via the Valiant-Vazirani lemma / isolation lemma. Is this the intended content of the question? In more detail: suppose there is an $\mathcal O(n^c)$ algorithm for Unique-SAT search. Given a SAT formula $\phi$, apply the Valiant-Vazirani reduction as usual: make new formulas $\phi_1,\ldots, \phi_n$ where $\phi_j=\phi\wedge \mathcal C$ where $C$ is a set of random constraints. Then whp at least one of the formulas has a unique satisfying assignment iff $\phi$ was satisfiable. Your algorithm will find it; its behaviour elsewhere is unimporant.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-07-03T19:17:50.180Z
@LieuweVinkhuijzen No, I am interested in consequences that yield deterministic efficient algorithm for Unique SAT (decision problem as defined in my post).
Mohammad Al-Turkistany
CC BY-SA 4.0
2022-07-04T06:29:22.083Z
Are you asking i)what happens when a Promise-UP problem has a polynomial time deterministic algorithm? [P=UP] ii) what happens when a US-complete problem has a polynomial time deterministic algorithm? [P=US]
Tayfun Pay
CC BY-SA 4.0
2022-07-04T11:33:55.587Z
Thanks, I see, that makes the question much more interesting. Tell me if I understand correctly. You want to know $UniqueSAT\in P^{PromiseUP}$, which is true iff $coNP\subseteq P^{PromiseUP}$, iff $NP\subseteq P^{PromiseUP}$. In other words, this happens iff the "$NP\subseteq P^{PromiseUP}$" result, aka the Valiant-Vazirani theorem, can be derandomized. Is that the intent of the question?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-07-04T12:56:17.200Z
@LieuweVinkhuijzen  The intent of the  post is to relate the complexity of the **decision** problem Unique SAT to that of the promise **search** problem unique 3SAT ( the promise is the input to the search problem has unique satisfying assignment).
Mohammad Al-Turkistany
CC BY-SA 4.0
2022-07-04T12:56:56.293Z
@TayfunPay No, see my comment above.
Mohammad Al-Turkistany
<cc.complexity-theory>
Consequences of efficient algorithm for search problem unique 3SAT
Mohammad Al-Turkistany
# Consequences of efficient algorithm for search problem unique 3SAT

(Asked by: username_0 on 2022-06-30)

The decision problem Unique SAT ={$\phi$  has unique satisfying assignment } represents a class of computational problems. P=NP iff Unique SAT is in P. Notice that Unique SAT is CoNP-hard and Unique SAT= SAT\ Double SAT ( Double SAT={$\phi$ has at least two satisfying assignments }).

Considering the search problem of finding the assignment that satisfies a uniquely satisfiable 3SAT formula (i.e. the promise is that the input formula is uniquely satisfiable). The best known algorithm is exponential. Unique 3-SAT can be solved in time $O(1.307^n)$ using a variation of PPSZ algorithm.

> Does an efficient algorithm for the search problem ( with Uniquness prommise) imply efficient deterministic algorithm for the decision problem Unique SAT?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Such a procedure would imply $NP\subseteq BPP$ via the Valiant-Vazirani lemma / isolation lemma. Is this the intended content of the question? In more detail: suppose there is an $\mathcal O(n^c)$ algorithm for Unique-SAT search. Given a SAT formula $\phi$, apply the Valiant-Vazirani reduction as usual: make new formulas $\phi_1,\ldots, \phi_n$ where $\phi_j=\phi\wedge \mathcal C$ where $C$ is a set of random constraints. Then whp at least one of the formulas has a unique satisfying assignment iff $\phi$ was satisfiable. Your algorithm will find it; its behaviour elsewhere is unimporant.  
> **username_0**: @LieuweVinkhuijzen No, I am interested in consequences that yield deterministic efficient algorithm for Unique SAT (decision problem as defined in my post).  
> **username_2**: Are you asking i)what happens when a Promise-UP problem has a polynomial time deterministic algorithm? [P=UP] ii) what happens when a US-complete problem has a polynomial time deterministic algorithm? [P=US]  
> **username_1**: Thanks, I see, that makes the question much more interesting. Tell me if I understand correctly. You want to know $UniqueSAT\in P^{PromiseUP}$, which is true iff $coNP\subseteq P^{PromiseUP}$, iff $NP\subseteq P^{PromiseUP}$. In other words, this happens iff the "$NP\subseteq P^{PromiseUP}$" result, aka the Valiant-Vazirani theorem, can be derandomized. Is that the intent of the question?  
> **username_0**: @LieuweVinkhuijzen  The intent of the  post is to relate the complexity of the **decision** problem Unique SAT to that of the promise **search** problem unique 3SAT ( the promise is the input to the search problem has unique satisfying assignment).  
> **username_0**: @TayfunPay No, see my comment above.  

---

## 0 answers

