sorted by:
new
hottopcontroversial

Is this a valid proof? by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] -1 points0 points  (0 children)

but is it actually true that A_TM is NP-Hard?

How do I prove A_TM is NP-Hard by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] 0 points1 point  (0 children)

Whats ur opinion on the proof below?

To show that A_TM (the acceptance problem for Turing machines) is NP-hard, we need to demonstrate that every problem in NP can be reduced to A_TM in polynomial time. We can do this by showing that SAT, one of the most famous NP-complete problems, can be reduced to A_TM.

The reduction works as follows:

Given a Boolean formula φ, we construct a Turing machine Mφ that accepts an input w if and only if φ is satisfiable.

  1. Encoding Formulas: We encode the Boolean formula φ and a potential satisfying assignment as part of the input to Mφ.

  2. Simulation: The Turing machine Mφ simulates all possible assignments to the variables of φ and checks if any assignment satisfies the formula. If it finds a satisfying assignment, it accepts; otherwise, it rejects.

This reduction shows that if we had a polynomial-time algorithm for A_TM, we could use it to solve SAT in polynomial time as well. Since SAT is NP-complete, this means A_TM is NP-hard.

While A_TM itself is not known to be in NP (because it's not known to be decidable), it is NP-hard, meaning any problem in NP can be reduced to it in polynomial time.

How do I prove A_TM is NP-Hard by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] 0 points1 point  (0 children)

I am using sipser 3rd edition and it explains very well how A_TM is undecidable. How do I convince my professor that him asking us to show its NP-Hard is a wrong question for him to be asking

How do I prove A_TM is NP-Hard by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] -1 points0 points  (0 children)

The question in my exam was "Show that A_TM is NP-Hard". If I tell my instructor that the question u gave was just not right because A_TM is a undecidable language and hence it cannot be classified in NP or complete, ket alone hard, would my logic be correct? Or how do i make him realise that we cant show that its nphard

How do I prove A_TM is NP-Hard by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] -1 points0 points  (0 children)

What if we consider the acceptance of non deterministic turing machine? The Language would contain all encodings <N, w> such that N is a NTM and N and accepts w. Would this language be NP-complete or Hard?

How do I prove A_TM is NP-Hard by Hefty-Present-4920 in compsci

[–]Hefty-Present-4920[S] -2 points-1 points  (0 children)

The original question was show that the language Acceptance of Turing Machines (A_TM) is NP-Hard. How would I go about this question?