Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?
share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

$\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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.