An Introduction to Formal Languages and Automata, 7th Edition

14.4 THE COMPLEXITY CLASSES P AND NP

At this point, it is instructive to summarize the difficulties we have encountered in trying to find useful complexity classes for formal languages and draw a few conclusions.

1. There exists an infinite number of properly nested complexity classes DTIME(n^k), k = 1,2, …. These complexity classes have little connection to the familiar Chomsky hierarchy, and it seems difficult to get any insight into the nature of these classes. Perhaps this is not a good way of classifying languages.
2. The particular model of Turing machine, even if we restrict ourselves to deterministic machines, affects the complexity. It is not clear what kind of Turing machine is the best model of an actual computer, so an analysis should ...