Computational Complexity Class

From GM-RKB
Jump to navigation Jump to search

A Computational Complexity Class is a automation-requiring task set that can be solved by an abstract machine $M$ using a Constructible Function $O(f(n))$ of a computational resource $R$.



References

2021

2020

  • (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Complexity_class Retrieved:2020-4-5.
    • … Complexity classes are concerned with the rate of growth of the requirement in resources as the input size n increases. It is an abstract measurement, and does not give time or space in requirements in terms of seconds or bytes, which would require knowledge of implementation specifics. The function inside the O(...) expression could be a constant, for algorithms which are unaffected by the size of n, or an expression involving a logarithm, an expression involving a power of n, i.e. a polynomial expression, and many others. The O is read as "order of..". For the purposes of computational complexity theory, some of the details of the function can be ignored, for instance many possible polynomials can be grouped together as a class.

      The resource in question can either be time, essentially the number of primitive operations on an abstract machine, or (storage) space. For example, the class NP is the set of decision problems whose solutions can be determined by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space.

2018

  • (Rao, 2018) ⇒ Anup Rao (October 11, 2018). "Lecture 5: Hierarchy Theorems".
    • QUOTE: But first, let us talk complexity classes. We are interested in classifying functions according to their complexity, so it makes sense to lump functions into sets of similar complexity:

      Definition 1. Define DTIME(t(n)) to be the set of functions [math]\displaystyle{ DTIME(t(n)) = \{ f : \{0, 1\}^∗ \to \{0, 1\}| \text{f is computable in time } O(t(n))\} }[/math].

      Similarly,

      Definition 2. Define DSPACE(s(n)) to be the set [math]\displaystyle{ DSPACE(s(n)) = \{ f : \{0, 1\}^∗ →\to \{0, 1\}| \text{f is computable in space }O(s(n))\} }[/math].

      Once we have these definitions, we can try to define what it means for a function of : \{0, 1\}^∗ \to \{0, 1\}$ to be efficiently computable.

2015

2006

1998