patternMinor
Does Max-SNP hard imply NP-hard
Viewed 0 times
implyhardmaxdoessnp
Problem
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:
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$.
- 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$.
Context
StackExchange Computer Science Q#6589, answer score: 8
Revisions (0)
No revisions yet.