4
$\begingroup$

Unique SAT is defined as:

Given any SAT problem, does the SAT problem have exactly 1 solution?

As I understand it is co-NPHard. I am unclear how it is in co-NP

  1. Assuming the problem has more than 1 solution, any 2 solutions can be a certificate of it being nonUnique. That part is coNP. Now, given a problem can be unsatisfiable, how do we get a certificate of no solution?

  2. Its also said that an NP Oracle can solve this problem in polynomial time, but an NP Oracle just tells if the problem is satisfiable. So how is that possible?

Apologies but I have no clue regarding this version of SAT.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

  1. To prove coNP-hardness, you don't need a certificate (that would be needed only if you wanted to show coNP-completeness). We just need some coNP-hard problem that reduces to UniqueSAT. UniqueSAT is indeed likely not in coNP.

  2. You can ask an oracle multiple queries. You could begin by asking if the formula has a satisfying assignment (and, using self-reduction, find a solution if one exists). Perhaps you can then use further queries to determine if another solution exists?

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. I just found this query. cstheory.stackexchange.com/questions/1639/… (1) I understood the certificate part. But as an answer states "problem of Unique satsifiability which is Co-NP-hard and and its in the class $DP=\{(L_1 ∩ L_2)| L_1 \in NP, L_2\in CoNP\}$ (the intersection of NP set with Co-NP set)." So, it seems its both in NP and coNP if I understand correctly. How does it affect the certificate part I am not sure (I think it should have a short certificate in both cases: true and false). And I don't know how ?! $\endgroup$
    – J.Doe
    Commented Jun 28, 2017 at 13:10
  • $\begingroup$ (2) Yes, I think we can ask multiple queries. So, if the first query says no solution then UniqueSAT is false. But, if it has a solution and it gives us one how do we ask for 'another' solution ? $\endgroup$
    – J.Doe
    Commented Jun 28, 2017 at 13:12
  • 1
    $\begingroup$ @J.Doe you can get the solution of a SAT from the oracle by modifying the SAT in such a way that you can find out part of the solution (by forcing a variable to be true or false for a solution to be valid) if at any point when a variable is forced to be true or false the oracle returns true for both cases then there are 2 solutions. $\endgroup$
    – ratchet freak
    Commented Jun 28, 2017 at 13:25
  • 1
    $\begingroup$ (1) No, it does not say it is in both $NP$ and $coNP$. It says it is the intersection of a language in $NP$ with a language in $coNP$. That is very different from saying it is in the intersection of $NP$ and $coNP$. $\endgroup$
    – Tom van der Zanden
    Commented Jun 28, 2017 at 20:47
  • 1
    $\begingroup$ @Turbo By reduction from UNSAT (i.e. the complement of SAT, which asks whether a given formula does not have any solutions). The idea is to modify the formula so that if it has no solutions, it will have exactly one unique solution, or if it has at least one solution, then it will have multiple. This can be done by adding a dummy variable $x$, so that setting $x$ to true will satisfy the formula but force all the other variables to a known setting, and that if $x$ is false then you get the original formula back. $\endgroup$
    – Tom van der Zanden
    Commented Jul 8, 2017 at 9:04
6
$\begingroup$
  1. You say it is coNP-hard. However, it tells nothing about whether it is contained in $\mathsf{coNP}$. It only says that it is at least as hard as any problem in $\mathsf{coNP}$.

This problem is known to be US-hard. $\mathsf{US}$ is not known to equal $\mathsf{coNP}$. It is only known to be a subset of $\mathsf{P^{NP}}$.

  1. You can find a solution $p$, add a clause that excludes that solution and see if it's satisfiable.

Let's say the formula $\Phi(x,~y,~z,~w)$ has a positive assignment $x,~\overline y,~\overline z,~w$. Now you just solve $\Phi \land (\overline x\lor y\lor z\lor\overline w)$. If it's satisfiable, your formula is not unique-SAT.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am a little confused regarding US complexity class vs. coNP. According to complexity zoo: "The class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts." So, as I understand every coNP problem can be transformed so that it has exactly one accepting path. If I understand correctly US is superset of coNP because there might be unique accepting paths that might be of exponential length, thus not in coNP? If yes can you please help with an example? $\endgroup$
    – J.Doe
    Commented Jun 28, 2017 at 15:47
  • $\begingroup$ And if that is not the only necessary and sufficient reason for a problem to be not in coNP but in US, can you please point it out ? $\endgroup$
    – J.Doe
    Commented Jun 28, 2017 at 15:50
  • 1
    $\begingroup$ @J.Doe, all paths are of polynomial size, since the problem is in $\mathsf{PSPACE}$. Reduction from not-3SAT to unique-SAT is possible, so, it contains $\mathsf{coNP}$: cs.stackexchange.com/questions/54529/… $\endgroup$
    – rus9384
    Commented Jun 28, 2017 at 16:05
  • $\begingroup$ Thank you. But, it still doesn't talk about the US is a superset of coNP part. Because, for that to happen we must have at least one problem that is not in coNP but is in US? do we have some example that satisfies the constraint ? $\endgroup$
    – J.Doe
    Commented Jun 28, 2017 at 16:11
  • $\begingroup$ @J.Doe, no, not every superset is strict superset. $\mathsf{coNP\subseteq US}$ just means that reduction from coNP-complete problem to US-complete problem is known. Nothing about $\mathsf{US \subsetneq coNP}$. $\endgroup$
    – rus9384
    Commented Jun 28, 2017 at 16:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.