Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Computational Complexity

Field: Theoretical Computer Science

The study of computational complexity.

Sequence of Expressions

For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME( nn ) is contained in DTIME( n2n^{2} ), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved. More precisely, the time hierarchy theorem states that DTIME(o(f(n)))⊊DTIME(f(n)⋅log⁡(f(n))){\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )} . The space hierarchy theorem states that DSPACE(o(f(n)))⊊DSPACE(f(n)){\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )} . The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.
Let TM\text{TM} denote the set of all deterministic Turing Machines. For any M and input xM \text{ and input } x, let TM(x)T_M(x) be the time complexity function, and SM(x)S_M(x) be the space complexity function. A language L is decidable in time O(f(n))L \text{ is decidable in time } O(f(n)) if there exists a TM M_L \text{ such that } L(M_L) = L \text{ and } T_{M_L}(x) \restrict{x \text{ length } n} \text{ is bounded by } c \text{ for some constant } c \text{ and } n \text{ large enough}.\n\nWe define the complexity class P\text{P} (Polynomial Time) as:\n\nP=⋃k is a positive integerPk\text{P} = \bigcup_{k \text{ is a positive integer}} \text{P}_k \n\nwhere Pk\text{P}_k is the set of all languages LL such that LL is decided by a TM MM whose running time TM(n)T_M(n) is bounded by O(nk)O(n^k). Formally, P=DTIME(poly(n))\text{P} = \text{DTIME}(\text{poly}(n)), where DTIME(f(n))=Alg(L) s.t. L is decided by a TM M with TM(n) bounded by f(n)\text{DTIME}(f(n)) = \text{Alg}(\text{L}) \text{ s.t. } \text{L} \text{ is decided by a TM } M \text{ with } T_M(n) \text{ bounded by } f(n).\n\nMore generally, the computational complexity of a problem A\text{A} is characterized by the minimal resource function f(n)f(n) such that $\text{A} \text{ belongs to } \text{DTIME}(f(n)) \text{ or } \text{DSPACE}(f(n)).