Skip to main content
added 43 characters in body
Source Link
Tsuyoshi Ito
  • 2.4k
  • 21
  • 15

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 there is nothing wrong hereyour proof for Question 2 does not contradict the answer to Question 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 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 there is nothing wrong here.

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.

Source Link
Tsuyoshi Ito
  • 2.4k
  • 21
  • 15

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 there is nothing wrong here.