# What is the computational complexity of this SAT Variant

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.

• 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. – Clement C. Jun 28 '17 at 10:20
• It is (But then again, K can be anything). I am trying to understand it in terms of certificates. – J.Doe Jun 28 '17 at 10:22
• 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? – J.Doe Jun 28 '17 at 11:27
• and what is the complexity of UniqueSAT. It seems to me we can solve it using an NP oracle in linear time or less? – J.Doe Jun 28 '17 at 11:29
• The problem "Exact-K-SAT" is ${\bf C_=P}$ complete. ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$. – Tayfun Pay Jun 29 '17 at 18:31

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.