patternMinor
Prove that $\text{EXACT-TRIPLE}$ is not in NP
Viewed 0 times
exacttripletextprovethatnot
Problem
I received the following assignment:
$\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?
$\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?
Solution
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.
Context
StackExchange Computer Science Q#7595, answer score: 9
Revisions (0)
No revisions yet.