Complexity Classes in DTIME
Many important complexity classes are defined in terms of DTIME, containing all of the problems that can be solved in a certain amount of deterministic time. Any proper complexity function can be used to define a complexity class, but only certain classes are useful to study. In general, we desire our complexity classes to be robust against changes in the computational model, and to be closed under composition of subroutines.
DTIME satisfies the time hierarchy theorem, meaning that asymptotically larger amounts of time always create strictly larger sets of problems.
The well-known complexity class P comprises all of the problems which can be solved in a polynomial amount of DTIME. It can be defined formally as:
P is the smallest robust class which includes linear-time problems (AMS 2004, Lecture 2.2, pg. 20). P is one of the largest complexity classes considered "computationally feasible".
A much larger class using deterministic time is EXPTIME, which contains all of the problems solvable using a deterministic machine in exponential time. Formally, we have
Larger complexity classes can be defined similarly. Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that, and on up.
Read more about this topic: DTIME
Famous quotes containing the words complexity and/or classes:
“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)
“My plan of instruction is extremely simple and limited. They learn, on week-days, such coarse works as may fit them for servants. I allow of no writing for the poor. My object is not to make fanatics, but to train up the lower classes in habits of industry and piety.”
—Hannah More (1745–1833)