Question

1. Show that Lacc is NP-Hard.

the definitions are below

x is any input to the program

Answer 1

Basically to show L_ACC is NP Hard we need to show any of the NP-Complete problem polynomial time reduce to an instance of L_ACC,as NP-complete problem covers the whole set of NP problem.

We know 3-SAT problem is a popular NP-Complete problem,and here we will transform an instance of 3-SAT to an instance of L_ACC.

As 3-SAT is a NP-Complete problem there must be a non-deterministic turing machine which can accept it,we will convert that non-deterministic turing machine to a deterministic turing machine say TM_2.

Now suppose for L_ACC we have an turing machine TM_1 which take <M,x> as input and halt if M accepts x.

we will give <TM_2,w> as a input to TM_1 ,where w is a input sequence T/F values for 3-SAT problem.

If TM_1 accept <TM_2,w>,that means w is a satisfiable assignment of T/F for 3-SAT problem.

Thus we can prove L_ACC is NP-Hard.