# Prove that $\text{EXACT-TRIPLE}$ is not in NP

$\text{EXACT-TRIPLE} = \{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \}$.

I need to decide whether this problem belongs to NP or not. I assume it does not. How do I prove that?

-
Are you shure that the assignment doesn't have a third option "Unknown"? :) –  Vor Dec 25 '12 at 18:23
The problem is coNP-hard, and so not likely to be in NP. Indeed, given a formula $\phi$, you can construct a formula $\phi'$ such that if $\phi$ has $x$ satisfying assignments then $\phi'$ has $x+3$. This gives a reduction from the coNP-complete problem UN-SAT to EXACT-TRIPLE.