HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.