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