<p>The sidebar algorithm has done its work, and linked to <a href="https://cstheory.stackexchange.com/questions/1965/hard-gaps-in-maximum-constraint-satisfaction-problems?rq=1">this similar question</a>. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist. </p>

CC BY-SA 4.0
2019-07-10T17:48:36.977Z
2019-07-10T17:48:36.977Z
Abel Molina
<p>I would like to know whether there are any examples of natural problems within the MAX-<span class="math-container">$k$</span>-CSP family for which (under standard/reasonable conjectures) we believe the following:</p>

<ul>
<li>There is a value <span class="math-container">$\epsilon_1$</span> such that approximation within a factor of <span class="math-container">$\epsilon_1$</span> is possible in polynomial time.</li>
<li>There is a value <span class="math-container">$\epsilon_2$</span> such that approximation within a factor of <span class="math-container">$\epsilon_2$</span> is NP-hard.</li>
<li>There is some value <span class="math-container">$\epsilon$</span> between <span class="math-container">$\epsilon_1$</span> and <span class="math-container">$\epsilon_2$</span> such that approximation within a factor of <span class="math-container">$\epsilon$</span> are neither in polynomial time nor NP-Hard.</li>
</ul>

<p>(There is a general question about NP-intermediate problems <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237">here</a>, but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)</p>

<approximation-algorithms><approximation-hardness><approximation><csp><np-intermediate>
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
Abel Molina
# NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

(Asked by: username_0 on 2019-05-21)

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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237), but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)

**Tags:** approximation-algorithms, approximation-hardness, approximation, csp, np-intermediate

---

## 1 answers

### Answer by username_0 on 2019-07-10. Score: 2

The sidebar algorithm has done its work, and linked to [this similar question](https://cstheory.stackexchange.com/questions/1965/hard-gaps-in-maximum-constraint-satisfaction-problems?rq=1). The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.


---

