- Let PTIME be the class of languages that can be decided in polynomial time, i.e., for any language in the class, there is a TM M and an integer s.t. for every input string of any length , M decides whether in time . Show that .
- Show that , i.e., a strict subset.
- Describe a TM D that takes as input the description of any TM M and input for M, and simulates M on and if M halts, it outputs the total number of steps taken in the simulation. What is the time complexity of your D as a function of the time complexity of M?

Advertisements