Problem 1: [True or False, with justification] (40 points) For each of the follo
ID: 3706723 • Letter: P
Question
Problem 1: [True or False, with justification] (40 points) For each of the following 5 questions,state TRUE or FALSE. If TRUE, give a short proof. If FALSE, give a simple counterexample. (a) The following language L is decidable: L = {?M) I M is a TM and, for all inputs w, M accepts w within 10000 steps) (b) If some regular language is NP-complete, then P NP. (e) Recall the proof of the Cook-Levin theorem, where we used legal 2 x 3 windows. suppose that the transition function ? of the TM we are encoding is such that (, a)(92, b, R) Then, the following 2 3 window is legal for machine M.Explanation / Answer
Solution:
a)
False
Explanation:
If the language is decidable then its all input strings it will be either accepted with a halt or rejected with a halt, and also there is no guarantee that the machine will stop in 10000 steps.
b)
True
Explanation:
Since the regular languages fall under P, which is solvable in polynomial time but if a problem is in NPC, then it will be proved that P= NP
e)
True.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)