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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“The most powerful lessons about ethics and morality do not come from school discussions or classes in character building. They come from family life where people treat one another with respect, consideration, and love.”
—Neil Kurshan (20th century)
“In comparison to the French Revolution, the American Revolution has come to seem a parochial and rather dull event. This, despite the fact that the American Revolution was successful—realizing the purposes of the revolutionaries and establishing a durable political regime—while the French Revolution was a resounding failure, devouring its own children and leading to an imperial despotism, followed by an eventual restoration of the monarchy.”
—Irving Kristol (b. 1920)
“The machines that are first invented to perform any particular movement are always the most complex, and succeeding artists generally discover that, with fewer wheels, with fewer principles of motion, than had originally been employed, the same effects may be more easily produced. The first systems, in the same manner, are always the most complex.”
—Adam Smith (1723–1790)