edited by
2,101 views
21 votes
21 votes

Let $A_{TM}$ be defined as follows:

$A_{TM}=\left \{ \left \langle M, w \right \rangle \mid \text{ The Turing machine $M$ accepts the word } w \right \}$

And let $L$ be some $\mathbf{NP}-$ complete language. Which of the following statements is FALSE?

  1. $L\in \mathbf{NP}$
  2. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$.
  3. Every problem in $\mathbf{NP}$ is polynomial time reducible to $A_{TM}$.
  4. Since $L$ is $\mathbf{NP}-$ complete, $A_{TM}$ is polynomial time reducible to $L$.
  5. $A_{TM} \notin \mathbf{NP}$.
edited by

2 Answers

Best answer
23 votes
23 votes

$\newcommand{NP}{\mathbf{NP}} \newcommand{NPC}{\mathbf{NPC}}$
$A_{TM}$ is the language of the Halting Problem. It is undecidable, but Recursively Enumerable.

$L$ is $\NPC$

  1. True. Any language in $\NPC$ is also in $\NP$ by definition.
  2. True. By definition, any problem in $\NP$ is polynomial time reducible to any $\NPC$ problem.
  3. True. $A_{TM}$ is undecidable. Any language that is decidable is polynomial time reducible to $A_{TM}$!
  4. False. $A_{TM}$ is undecidable. No Turing Machine can guarantee an answer in a finite time, let alone a polynomial time.
  5. True. $A_{TM}$ is undecidable. It is certainly not in $\NP$.

Hence, the correct answer is option d.

edited by
1 votes
1 votes

L is NPC, so by definition L belongs to NP and every problem in NP reduces to L in polynomial time. Options A and B are True,


$A_{TM}$ describes the famous Halting problem which is undecidable.

Undecidable languages are harder than decidable languages (P and NP), hence, every problem in NP is polynomial time reducible to $A_{TM}$

But, the converse is not true. Harder problems can't be reduced to easier problems in polynomial time.

Hence, C is True, but D is False (Answer)


$A_{TM}$ is undecidable. NP and P are the subdivisions of the decidable zone. Undecidable isn't included in it. Option E is True.

Answer:

Related questions