<p>I am trying to wrap my head around implications of CSP dichotomy theroem.
CSP is short for Constraint Satisfaction Problem.
The following seem to be known results (I shall focus on decision problems that take only a graph as input, for definiteness).</p>
<p>For every decision problem <span class="math-container">$P$</span> that takes a graph <span class="math-container">$G$</span> as input,</p>
<ul>
<li><span class="math-container">$P$</span> is NP-complete <span class="math-container">$\implies$</span> <span class="math-container">$P$</span> is a CSP.</li>
<li><span class="math-container">$P$</span> is a CSP <span class="math-container">$\implies$</span> <span class="math-container">$P$</span> is not in NPI (i.e., NP-Intermediate).</li>
</ul>
<p>We say that <span class="math-container">$P$</span> is in NPC (resp. NPI, or P) for graph class <span class="math-container">$\mathscr{G}$</span> if the problem <span class="math-container">$P$</span> is in NPC (resp. NPI, or P) when the input graph <span class="math-container">$G$</span> is (guaranteed to be) from <span class="math-container">$\mathscr{G}$</span>.</p>
<p><strong>Is there an error in the following argument that &quot;<span class="math-container">$P$</span> is NP-complete for a graph class <span class="math-container">$\mathscr{G}$</span> <span class="math-container">$\implies$</span> <span class="math-container">$P$</span> is not NP-intermediate for any graph class <span class="math-container">$\mathscr{H}$</span> &quot;?</strong><br />
Suppose that <span class="math-container">$P$</span> is NP-complete for a graph class <span class="math-container">$\mathscr{G}$</span>. Then, <span class="math-container">$P$</span> is NP-complete in general (i.e. no restriction on input graph). Hence, <span class="math-container">$P$</span> is in CSP (in general graphs). As a result, for every graph class <span class="math-container">$\mathscr{H}$</span>, <span class="math-container">$P$</span> in CSP even when input graph is from <span class="math-container">$\mathscr{H}$</span>. Therefore, <span class="math-container">$P$</span> is not NP-intermediate for any graph class <span class="math-container">$\mathscr{H}$</span>.</p>

CC BY-SA 4.0
2022-05-05T08:38:42.327Z
There seems to be a lot of confusions and I have trouble understanding both your reasoning and question. What do you mean by "P is a CSP"? The dichotomy theorem states that for every signature $\Sigma$ the *problem* $CSP(\Sigma)$ is either in P or NP-complete. It does not say anything on the structure of the input.
holf
CC BY-SA 4.0
2022-05-05T09:03:40.387Z
@holf A problem $P$ is a CSP if there exist a signature $\Sigma$ such that $P$ is equivalent to $CSP(\Sigma)$.
Cyriac Antony
CC BY-SA 4.0
2022-05-05T09:07:06.187Z
The dichotomy theorem does not hold if you impose additional constraints on the input. This creates a different computational problem that is no longer just a CSP.
Emil Jeřábek
CC BY-SA 4.0
2022-05-05T09:39:51.717Z
As a matter of fact, for an arbitrary NP-language $A$, there is a CSP $P$ on graphs and a suitable graph class $\mathcal G$ such that $P$ restricted to $\mathcal G$ (as a promise problem) has the same complexity as $A$ (up to polynomial-time many-one reductions). Take for $P$ a paddable NP-complete CSP such as $3$-COLOURABILITY. Then there exists a poly-time reduction $f$ of $A$ to $P$ with a poly-time left inverse, and we can define $\mathcal G$ as the image of $f$. Thus, if P $\ne$ NP, there are infinitely many inequivalent NP-intermediate problems of this form by Ladner’s theorem.
Emil Jeřábek
CC BY-SA 4.0
2022-05-10T10:15:00.930Z
If I'm not mistaken, CSP problems are homomorphism-closed, in the sense that if $G$ is a positive instance and $G'$ has a homomorphism to $G$ then $G'$ is also a positive instance, because homomorphisms compose. But arbitrary NP-complete problems on graphs aren't necessarily homomorphism-closed. So it can't be the case that every NP-complete problem on graphs is equivalent to a CSP, right?
Antoine Amarilli 'a3nm'
<cc.complexity-theory><complexity-classes><csp>
Does NP-completeness in one graph class imply not NP-intermediate in another graph class?
Cyriac Antony
# Does NP-completeness in one graph class imply not NP-intermediate in another graph class?

(Asked by: username_0 on 2022-05-05)

I am trying to wrap my head around implications of CSP dichotomy theroem.
CSP is short for Constraint Satisfaction Problem.
The following seem to be known results (I shall focus on decision problems that take only a graph as input, for definiteness).

For every decision problem $P$ that takes a graph $G$ as input,

* $P$ is NP-complete $\implies$ $P$ is a CSP.
* $P$ is a CSP $\implies$ $P$ is not in NPI (i.e., NP-Intermediate).

We say that $P$ is in NPC (resp. NPI, or P) for graph class $\mathscr{G}$ if the problem $P$ is in NPC (resp. NPI, or P) when the input graph $G$ is (guaranteed to be) from $\mathscr{G}$.

**Is there an error in the following argument that "$P$ is NP-complete for a graph class $\mathscr{G}$ $\implies$ $P$ is not NP-intermediate for any graph class $\mathscr{H}$ "?**  
Suppose that $P$ is NP-complete for a graph class $\mathscr{G}$. Then, $P$ is NP-complete in general (i.e. no restriction on input graph). Hence, $P$ is in CSP (in general graphs). As a result, for every graph class $\mathscr{H}$, $P$ in CSP even when input graph is from $\mathscr{H}$. Therefore, $P$ is not NP-intermediate for any graph class $\mathscr{H}$.

**Tags:** cc.complexity-theory, complexity-classes, csp

> **Comments:**
> **username_1**: There seems to be a lot of confusions and I have trouble understanding both your reasoning and question. What do you mean by "P is a CSP"? The dichotomy theorem states that for every signature $\Sigma$ the *problem* $CSP(\Sigma)$ is either in P or NP-complete. It does not say anything on the structure of the input.  
> **username_0**: @username_1 A problem $P$ is a CSP if there exist a signature $\Sigma$ such that $P$ is equivalent to $CSP(\Sigma)$.  
> **username_2**: The dichotomy theorem does not hold if you impose additional constraints on the input. This creates a different computational problem that is no longer just a CSP.  
> **username_2**: As a matter of fact, for an arbitrary NP-language $A$, there is a CSP $P$ on graphs and a suitable graph class $\mathcal G$ such that $P$ restricted to $\mathcal G$ (as a promise problem) has the same complexity as $A$ (up to polynomial-time many-one reductions). Take for $P$ a paddable NP-complete CSP such as $3$-COLOURABILITY. Then there exists a poly-time reduction $f$ of $A$ to $P$ with a poly-time left inverse, and we can define $\mathcal G$ as the image of $f$. Thus, if P $\ne$ NP, there are infinitely many inequivalent NP-intermediate problems of this form by Ladner’s theorem.  
> **username_3**: If I'm not mistaken, CSP problems are homomorphism-closed, in the sense that if $G$ is a positive instance and $G'$ has a homomorphism to $G$ then $G'$ is also a positive instance, because homomorphisms compose. But arbitrary NP-complete problems on graphs aren't necessarily homomorphism-closed. So it can't be the case that every NP-complete problem on graphs is equivalent to a CSP, right?  

---

## 0 answers

