1
$\begingroup$

I'm having a very hard time understanding what's what.

$$L_{1}\leq_{p}L_{2}$$

If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete? I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

I say (and I could be wrong - and that's a strong possiblity since I have very little understanding of this material) that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

$\endgroup$
7
$\begingroup$

You asked two questions. What you are missing is that those two questions are unrelated.

Question 1:

$$L_{1}\leq_{p}L_{2}$$

If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete?

No. Consider the case where L1 and L2 are the same easy problem.

Question 2:

I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

I say […] that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

There is nothing wrong with your proof. (Okay, I would not call the exponential-time simulation of a nondeterministic polynomial-time Turing machine “breadth-first search,” but that is a separate issue.) As your fellow student said, it is true that you cannot claim that L1 is NP-complete, and indeed you have never claimed that L1 is NP-complete, so your proof for Question 2 does not contradict the answer to Question 1.

$\endgroup$
  • $\begingroup$ How would you describe the algorithm then, without using the term breadth-first-search? I've read that in my textbook by Sipser and my class notes from the prof. I guess you could call it a level-order traversal of the computation tree, but that's just semantics. $\endgroup$ – agent154 Feb 20 '13 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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