Computational Complexity: Article 4
Equations Speak Louder Than Words
We have thus far created a strong link between familiar intuition and formal mathematics, with the intent of constructing a framework with which to better analyse and understand the complexity of computations. We continue on this trajectory by classifying decision problems according to the resources they consume on deterministic (for the same input, will always produce the same output on different runs) and non-deterministic (for the same input, can produce different outputs on different runs) Turing machines. Our resource of consideration will be time, T(n), called time complexity, where n is input length. A similar analysis can be done for space or memory.
Definition 4.1 Let T(n): N → N (T(n)‘s domain and codomain is the set of Naturals) be a proper time function. Then DTIME(T(n)) is the time complexity class containing languages that can be recognized by deterministic Turing machines (DTM’s) that halt on all inputs in time T(n), where n is the length of an input.…