0
$\begingroup$

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," 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!

$\endgroup$
4
  • $\begingroup$ 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?) $\endgroup$
    – D.W.
    Dec 13, 2023 at 7:30
  • $\begingroup$ @D.W. input: a satisfiable cnf formula. output: yes/no indicting if the given cnf formula has a unique solution. $\endgroup$
    – Jxb
    Dec 13, 2023 at 7:33
  • 4
    $\begingroup$ This is coNP-complete. (Easy exercise.) $\endgroup$ Dec 13, 2023 at 9:16
  • $\begingroup$ "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. $\endgroup$
    – rus9384
    Dec 13, 2023 at 18:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.