TIFR CSE 2011 | Part B | Question: 25

Question

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?

• A. $L\in \mathbf{NP}$
• B. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$.
• C. Every problem in $\mathbf{NP}$ is polynomial time reducible to $A_{TM}$.
• D. Since $L$ is $\mathbf{NP}-$ complete, $A_{TM}$ is polynomial time reducible to $L$.
• E. $A_{TM} \notin \mathbf{NP}$.

Answer 1

$\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.

Comments

@Pragy Agarwal Sir

plz check this

In option C)  "Every problem in NP is polynomial time reducible to $A_{TM}$"

Now, we know, every NP problem is Recursive. And according to explanation given $A_{TM}$ is an acceptance problem, i.e. Recursive Enumerable. That means every recursive problem, polynomially reducible to recursive enumerable problem. That mean RE is at least as hard as REC problem.

Am I right??

---

@srestha ma'am, is Atm np hard? i am not able to understand option d and also cannot understand why every decidable problem is reducible to an undecidable problem. can u suggest any good resource for it?

---

@ayush.5 check this.

https://gatecse.in/p-np-np-complete-np-hard/

Answer 2

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.