Problem Detail: I have difficulties understanding the definition of the class Max-SNP (optimization variant of strict NP), thus I have to following basic question:
If a problem is known to be Max-SNP hard, does this imply NP-hardness of the problem?
Asked By : mat
Answered By : Nicholas Mancuso
$newcommand{maxsnp}{mathsf{Max}text{-}mathsf{SNP}}$The definition of $maxsnp$ gives us the ability to define:
- Universal ($forall$) and existential ($exists$) quantifiers over variables
- Existential quantifiers over relations
With this definition we can define $mathsf{Max}$-$mathsf{SAT}$: $$exists x, forall y text{ such that } |psi(y)| leq |psi(x)|$$ where $|psi(x)|$ is the number of clauses satisfied in formula $psi$ under assignment $x$. Given that $mathsf{Max}$-$mathsf{SAT}$ is $mathsf{NP}$-$mathsf{Hard}$, we see that $mathsf{NP}$-$mathsf{Hardness}$ is implied from $maxsnp$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6589
