<p>I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances.</p>
<p><strong>input and output:</strong> input: A satisfiable cnf formula. output: yes/no indicating if the given cnf formula has an unique solution.</p>
<p><strong>Background:</strong> In the paper <a href="https://www.sciencedirect.com/science/article/pii/0304397586901350" rel="nofollow noreferrer">&quot;NP is as easy as detecting unique solutions,&quot;</a> it is stated that distinguishing between instances of SAT that have zero or one solution is as hard as SAT itself, under randomized reductions. Based on this, I am interested in understanding the complexity involved specifically in identifying uniquely solvable SAT problems from those that are merely satisfiable.</p>
<p><strong>Question:</strong> What is the known computational complexity of identifying a SAT problem with exactly one solution from a set of SAT problems that are known to be satisfiable? Are there any established results or theories that describe this complexity?</p>
<p>Thank you for your insights!</p>

CC BY-SA 4.0
2023-12-13T07:30:42.957Z
What do you mean by "identifying"?  What is the input to the algorithm, and what is the desired output?  What is promised/guaranteed about the input?  (e.g., that at least one of the instances has exactly one solution?)
D.W.
CC BY-SA 4.0
2023-12-13T07:33:05.250Z
@D.W. input: a satisfiable cnf formula.  output: yes/no  indicting if the given cnf formula has a unique solution.
Jxb
CC BY-SA 4.0
2023-12-13T09:16:44.610Z
This is coNP-complete.  (Easy exercise.)
Emil Jeřábek
CC BY-SA 4.0
2023-12-13T18:37:54.527Z
"I am interested in understanding the complexity involved specifically in identifying uniquely solvable SAT problems from those that are merely satisfiable." There is a complexity class, called US. It does not have a promise for the input formula being satisfiable, however, so is both NP- and coNP-hard.
rus9384
<np-hardness><sat><reductions><complexity>
Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances
Jxb
# Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances

(Asked by: username_0 on 2023-12-13)

I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances.

**input and output:** input: A satisfiable cnf formula. output: yes/no indicating if the given cnf formula has an unique solution.

**Background:** In the paper ["NP is as easy as detecting unique solutions,"](https://www.sciencedirect.com/science/article/pii/0304397586901350) it is stated that distinguishing between instances of SAT that have zero or one solution is as hard as SAT itself, under randomized reductions. Based on this, I am interested in understanding the complexity involved specifically in identifying uniquely solvable SAT problems from those that are merely satisfiable.

**Question:** What is the known computational complexity of identifying a SAT problem with exactly one solution from a set of SAT problems that are known to be satisfiable? Are there any established results or theories that describe this complexity?

Thank you for your insights!

**Tags:** np-hardness, sat, reductions, complexity

> **Comments:**
> **username_1**: What do you mean by "identifying"?  What is the input to the algorithm, and what is the desired output?  What is promised/guaranteed about the input?  (e.g., that at least one of the instances has exactly one solution?)  
> **username_0**: @username_1 input: a satisfiable cnf formula.  output: yes/no  indicting if the given cnf formula has a unique solution.  
> **username_2**: This is coNP-complete.  (Easy exercise.)  
> **username_3**: "I am interested in understanding the complexity involved specifically in identifying uniquely solvable SAT problems from those that are merely satisfiable." There is a complexity class, called US. It does not have a promise for the input formula being satisfiable, however, so is both NP- and coNP-hard.  

---

## 0 answers

