<p>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)$. <p> 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. <p> It is known that ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$ <p> See the paper "On the Power of Deterministic Reductions to ${\bf C_=P}$ " by Frederic Green. </p>

CC BY-SA 3.0
2017-07-03T19:08:30.130Z
2017-07-03T19:08:30.130Z
Tayfun Pay
<p>Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'?</p>

<p>Now, lets say K=1 (without loss of generality).</p>

<ol>
<li><p>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.  </p></li>
<li><p>If the answer is False. Then either it has 0 or more than 1 solution.</p>

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

<p>(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.</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2017-06-28T10:20:58.313Z
Isn't the case $K=1$ exactly UNIQUE-SAT (which is complete for [US](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us))? Then you have coNP $\subseteq$ US, not the other way around.
Clement C.
CC BY-SA 3.0
2017-06-28T10:22:45.783Z
It is (But then again, K can be anything). I am trying to understand it in terms of certificates.
J.Doe
CC BY-SA 3.0
2017-06-28T11:27:41.237Z
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
CC BY-SA 3.0
2017-06-28T11:29:16.670Z
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
CC BY-SA 3.0
2017-06-29T18:31:44.330Z
The problem "Exact-K-SAT" is ${\bf C_=P}$ complete. ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$.
Tayfun Pay
CC BY-SA 3.0
2017-06-29T18:35:29.420Z
Add one accepting path and query the ${\bf US}$ oracle... if it accepts then the original input had no satisfying truth assignments.
Tayfun Pay
<cc.complexity-theory><np-hardness>
What is the computational complexity of this SAT Variant
J.Doe
# What is the computational complexity of this SAT Variant

(Asked by: username_0 on 2017-06-28)

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.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: Isn't the case $K=1$ exactly UNIQUE-SAT (which is complete for [US](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us))? Then you have coNP $\subseteq$ US, not the other way around.  
> **username_0**: It is (But then again, K can be anything). I am trying to understand it in terms of certificates.  
> **username_0**: 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?  
> **username_0**: and what is the complexity of UniqueSAT. It seems to me we can solve it using an NP oracle in linear time or less?  
> **username_2**: The problem "Exact-K-SAT" is ${\bf C_=P}$ complete. ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$.  
> **username_2**: Add one accepting path and query the ${\bf US}$ oracle... if it accepts then the original input had no satisfying truth assignments.  

---

## 1 answers

### Answer by username_2 on 2017-07-03. Score: 5 | Accepted answer

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.


---

