1
$\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.

$\endgroup$
4
$\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?

$\endgroup$
  • $\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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 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 Jul 8 '17 at 9:04
4
$\begingroup$

1) You say it is coNP-hard. However, it tells nothing about the fact if it is $\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 equals $\mathsf{coNP}$. It is only known to be a subset of $\mathsf{P^{NP}}$.

2) You can find a solution $p$, add clause that contains that solution and see if it's satisfiable.

Let's say 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.

$\endgroup$
  • $\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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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