Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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. –  agent154 Feb 20 '13 at 20:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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