Theory (11 points). In the blanks mark each of the statements below as true (T) or false (F).

A. _____ No RE matches a string shorter than itself. B. _____ Any RE without closure (* or +) describes only finitely many strings. C. _____ No problem in NP can be solved in polynomial time. D. _____ It is possible to write a program that goes into an infinite loop if a given Java program goes into an infinite loop and terminates otherwise. E. _____ If P equals NP, every problem in NP is NP-complete.

F. _____ No Turing machine can decide whether a given DFA halts on an arbitrary finite input. G. _____ The Church-Turing thesis cannot be proven mathematically. H. _____ If P equals NP, then the Traveling Salesperson Problem can be solved in polynomial time by a deterministic Turing Machine. I. _____ If P does not equal NP, then the Traveling Salesperson Problem is not in P. J. _____ Factoring is known to be in NP but has not been proven to be NP-complete. K. _____ The discovery of a polynomial-time algorithm for TSP would not imply a polynomial-time algorithm for factoring.