# NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

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)

## 1 Answer

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.