10
$\begingroup$

Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP? Thanks

$\endgroup$
3
  • 3
    $\begingroup$ In general, there is no interesting relationship between inclusion and computational hardness. If $A ⊆ B$, then $A$ could be a lot harder to decide than $B$ (e.g., $A$ = "is there a Hamiltonian path from s to t" and $B$ = "is there a path from s to t") or a lot easier (e.g., $A$ = "is the graph strongly connected" and $B$ = "is there a Hamiltonian path from s to t"). $\endgroup$ Commented Mar 12 at 9:45
  • 3
    $\begingroup$ @JeanAbouSamra: Quite right, except that I think you mean "complete" rather than "strongly connected". A strongly connected graph need not contain any Hamiltonian paths at all; for example, it might have one "central" vertex with edges to and from every other vertex, but with no edges between any of those other vertices. $\endgroup$
    – ruakh
    Commented Mar 12 at 20:59
  • $\begingroup$ Yeah, you're right of course, sorry for the mixup. $\endgroup$ Commented Mar 13 at 8:12

4 Answers 4

24
$\begingroup$

Consider the following problems:

  • $L_1$:
    • Input: two graphs $G_1$ and $G_2$
    • Question: does $G_1$ contain an hamiltonian path and is $G_2$ complete?
  • $L_2$:
    • Input: two graphs $G_1$ and $G_2$
    • Question: is $G_2$ complete?
  • $L_3$:
    • Input: two graphs $G_1$ and $G_2$
    • Question: does $G_2$ contain an hamiltonian path?

Then $L_1 \subseteq L_2 \subseteq L_3$. $L_1$ and $L_3$ are $\mathsf{NP}$-complete, but $L_2$ is in $\mathsf{P}$.

$\endgroup$
20
$\begingroup$

That’s trivial. Take an NP-complete language $L$ with three symbols $a, b$, and $c$. Let $L’$ be the same language with $a, b, c$ replaced with $d, e, f$.

Now pick $L_1 = L, L_2 = (a \cup b \cup c)^*$, and $L_3 = L_2 (\epsilon \cup L’)$.

$\endgroup$
18
$\begingroup$

The existing answers provide good examples of the requested condition, but I think there's some intuition missing.

What makes a language hard to decide is not what it contains, but the combination of what it contains and does not contain. That is, it is the "shape" of the language boundary that makes it hard.

With that in mind, a procedure for obtaining the condition $L1 \subseteq L2 \subseteq L3$ is:

  • Pick any NP-complete $L1$, e.g., the set of all satisfiable boolean formulae.

  • Form $L2$ by expanding $L1$ to a simple superset, e.g., the set of all boolean formulae (regardless of satisfiability).

  • Form $L3$ by expanding $L2$, adding another difficult boundary. For example, elements of $L3$ can consist of an element of $L2$ optionally followed by an element of any NP-complete language (including $L1$ again).

Graphically, this looks like:

Jagged L1 inside smooth L2 inside jagged L3

In this diagram, the smooth boundary of $L2$ is meant to suggest it is easy to recognize, while the more jagged boundaries of $L1$ and $L3$ suggest they are hard to recognize.

$\endgroup$
9
$\begingroup$

The constructions in the other answers are nice, but end up with somewhat artificial languages created by disjunction. There are more natural languages that also do the trick:

Let $L_1$ be the set of trees that can be embedded in the 2D integer grid, such that the vertices are placed on distinct grid points and the edges are placed on grid edges. (This is an NP-complete problem, see this answer ).

Let $L_2$ be the set of all trees (clearly in P), and let $L_3$ be the set of $3$-colorable graphs (well-known to be NP-complete).

$L_1\subseteq L_2$ should be clear, and $L_2\subseteq L_3$ follows from the fact that all trees are $2$-colorable.

$\endgroup$
2
  • $\begingroup$ Very nice. I like that the first problem L1 is very little known. L3 is a bit better known (and it is interesting that 2, 3 and 4 colorability are so different), and L2 is not trivial like mine. $\endgroup$
    – gnasher729
    Commented Mar 15 at 0:11
  • 1
    $\begingroup$ I wouldn't say 3 or 4-colourability is that different, except on planar graphs, of course. But now I notice you can use the 4-colour theorem to not only get a new list, but expand the first list: let $L_3:=$ 3-colourable planar graphs, $L_4:=$ 4-colourable planar graphs, $L_5:=$ 4-colourable graphs. $\endgroup$
    – Discrete lizard
    Commented Mar 15 at 9:52

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.