Assessing complexity of a language using subset relations

Question

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.

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.