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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.