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)
“Classes struggle, some classes triumph, others are eliminated. Such is history; such is the history of civilization for thousands of years.”
—Mao Zedong (1893–1976)
“What is man in nature? A nothing in comparison with the infinite, an all in comparison with the nothing—a mean between nothing and everything.”
—Blaise Pascal (1623–1662)
“If men do not keep on speaking terms with children, they cease to be men, and become merely machines for eating and for earning money.”
—John Updike (b. 1932)