Does Max-SNP hard imply NP-hard
-
16-10-2019 - |
Question
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?
Solution
$\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$.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange