1
$\begingroup$

Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'?

Now, lets say K=1 (without loss of generality).

  1. If the problem has a exactly 1 solution and the answer is True. So, the partial certificate is that 1 solution. the certificate is partial as it shows there is a solution but without guarantee of exactly 1.

  2. If the answer is False. Then either it has 0 or more than 1 solution.

    (a) In case of more than 1 solution, the certificate is any of the 2 or more solutions. This is a complete certificate.

    (b) In case of 0 solution, the problem is same as asking does the given SAT have a solution. The certificate being same in 1.

Thus, the problem seems to require a certificate from both NP and co-NP versions. It seems to mean problem lies in NP and co-NP. But then it also is NP-hard. So doesn't that imply NP=co-NP?! What am I missing.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Isn't the case $K=1$ exactly UNIQUE-SAT (which is complete for US)? Then you have coNP $\subseteq$ US, not the other way around. $\endgroup$ – Clement C. Jun 28 '17 at 10:20
  • $\begingroup$ It is (But then again, K can be anything). I am trying to understand it in terms of certificates. $\endgroup$ – J.Doe Jun 28 '17 at 10:22
  • $\begingroup$ I am even more confused. US is a class that has exactly one accepting path as I understand. co-NP are the problems whose NP versions have certificates for yes/true solutions that can be checked in Polynomial time. There can be 1 or more certificates. So, how is coNP ⊆ US? $\endgroup$ – J.Doe Jun 28 '17 at 11:27
  • $\begingroup$ and what is the complexity of UniqueSAT. It seems to me we can solve it using an NP oracle in linear time or less? $\endgroup$ – J.Doe Jun 28 '17 at 11:29
  • $\begingroup$ The problem "Exact-K-SAT" is ${\bf C_=P}$ complete. ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$. $\endgroup$ – Tayfun Pay Jun 29 '17 at 18:31
5
$\begingroup$

The class ${\bf C_=P}$ is defined to be the set of languagges $L$ such that there exist functions $f \in {\bf \# P}$,$t\in {\bf FP} $ and for all $x, x\in L$ if and only if $f(x)=t(x)$.

Exact-SAT is the standard complete language for ${\bf C_=P}$. Exact-SAT = $\{F, k\} | F$ is a Boolean formula with exactly $k$ satisfying truth assignments.

It is known that ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$

See the paper "On the Power of Deterministic Reductions to ${\bf C_=P}$ " by Frederic Green.

|cite|improve this answer
$\endgroup$

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.