Polynomial time reductions

Question

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?

Answer 1

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 L₁ and L₂ 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 L₁ is NP-complete, and indeed you have never claimed that L₁ is NP-complete, so your proof for Question 2 does not contradict the answer to Question 1.