Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 6 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|cite|improve this answer

Your Answer


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.