Complexity Classes and Comparison To Deterministic Turing Machines
The following complexity classes are useful to define for ATMs:
- are the languages decidable in polynomial time
- are the languages decidable in polynomial space
- are the languages decidable in exponential time
These are similar to the definitions of P, PSPACE, and EXPTIME, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer proved the theorems
- AP = PSPACE
- APSPACE = EXPTIME
- AEXPTIME = EXPSPACE
When and This is expressed by the Parallel computation thesis.
Read more about this topic: Alternating Turing Machine
Famous quotes containing the words complexity, classes, comparison and/or machines:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“... too much attention is paid to dress by those who have neither the excuse of ample means nor of social claims.... The injury done by this state of things to the morals and the manners of our lower classes is incalculable.”
—Mrs. H. O. Ward (1824–1899)
“The difference between human vision and the image perceived by the faceted eye of an insect may be compared with the difference between a half-tone block made with the very finest screen and the corresponding picture as represented by the very coarse screening used in common newspaper pictorial reproduction. The same comparison holds good between the way Gogol saw things and the way average readers and average writers see things.”
—Vladimir Nabokov (1899–1977)
“The machine has had a pernicious effect upon virtue, pity, and love, and young men used to machines which induce inertia, and fear, are near impotents.”
—Edward Dahlberg (1900–1977)