4
$\begingroup$

I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:

  • There is a value $\epsilon_1$ such that approximation within a factor of $\epsilon_1$ is possible in polynomial time.
  • There is a value $\epsilon_2$ such that approximation within a factor of $\epsilon_2$ is NP-hard.
  • There is some value $\epsilon$ between $\epsilon_1$ and $\epsilon_2$ such that approximation within a factor of $\epsilon$ are neither in polynomial time nor NP-Hard.

(There is a general question about NP-intermediate problems here, but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.