[Solved]: Does Max-SNP hard imply NP-hard

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:

1. Universal ($\forall$) and existential ($\exists$) quantifiers over variables
2. 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