<p>The statement is unlikely to be true since we can deduce NP-hardness for Graph Isomorphism from it (which would imply a collapse of PH to its second level) as follows:</p>

<p>Let SGI be the Subgraph Isomorphism problem which is known to be NP-complete. Then GI is a subset of SGI. Now, take HAMCIRC and define a slightly different version:</p>

<p>ISO-HAMCIRC = $\{ (G_1, G_2) | G_1 \text{ is isomorph to } G_2 \text{ and } G_1 \in \text{HAMCIRC} \}$ </p>

<p>It is trivial to see that ISO-HAMCIRC is NP-complete as well. </p>

<p>It follows that ISO-HAMCIRC $\subseteq$ GI $\subseteq$ SGI and therefore GI would be NP-hard assuming the hypothesis holds.</p>

CC BY-SA 3.0
2014-01-03T11:10:11.270Z
2014-01-03T11:10:11.270Z
John D.
<p>What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate selection of a subset of $\Sigma^*$.</p>

<p>I would try to formalize this intuition as the following statement:</p>

<p>Let $A,B$ be two languages which are complete w.r.t to some class $\mathcal{C}$. Then for every language $C$ it holds that
$$ A \subseteq C \subseteq B \implies C \text{ is complete w.r.t $\mathcal{C}$} $$</p>

<p>What can we say about the truth value of this statement or interesting special cases such as NP. Maybe it implies only lower bounds(hardness)?
I would be rather suprised if even the lower bounds of $A$ and $B$ don't apply to $C$. </p>

<p>One natural example to explore might be HAMCIRC and HAMPATH. If the hypotheses holds then we could state that any set of graphs $G$ for which every element has a hampath and every graph with a hamcirc is contained in it, it follows that $G$ is NP-complete. </p>

<cc.complexity-theory><fl.formal-languages>
Assessing complexity of a language using subset relations
John D.
# Assessing complexity of a language using subset relations

(Asked by: username_0 on 2014-01-03)

What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate selection of a subset of $\Sigma^\*$.

I would try to formalize this intuition as the following statement:

Let $A,B$ be two languages which are complete w.r.t to some class $\mathcal{C}$. Then for every language $C$ it holds that
$$ A \subseteq C \subseteq B \implies C \text{ is complete w.r.t $\mathcal{C}$} $$

What can we say about the truth value of this statement or interesting special cases such as NP. Maybe it implies only lower bounds(hardness)?
I would be rather suprised if even the lower bounds of $A$ and $B$ don't apply to $C$.

One natural example to explore might be HAMCIRC and HAMPATH. If the hypotheses holds then we could state that any set of graphs $G$ for which every element has a hampath and every graph with a hamcirc is contained in it, it follows that $G$ is NP-complete.

**Tags:** cc.complexity-theory, fl.formal-languages


---

## 1 answers

### Answer by username_0 on 2014-01-03. Score: 3 | Accepted answer

The statement is unlikely to be true since we can deduce NP-hardness for Graph Isomorphism from it (which would imply a collapse of PH to its second level) as follows:

Let SGI be the Subgraph Isomorphism problem which is known to be NP-complete. Then GI is a subset of SGI. Now, take HAMCIRC and define a slightly different version:

ISO-HAMCIRC = $\{ (G\_1, G\_2) | G\_1 \text{ is isomorph to } G\_2 \text{ and } G\_1 \in \text{HAMCIRC} \}$

It is trivial to see that ISO-HAMCIRC is NP-complete as well.

It follows that ISO-HAMCIRC $\subseteq$ GI $\subseteq$ SGI and therefore GI would be NP-hard assuming the hypothesis holds.


---

