Computational Complexity Class
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$.
- Context:
- It can range from being a Time-Complexity Class to being Space-Complexity Class.
- …
- Example(s):
- TC0 (Threshold Circuit of depth 0): Tasks that involve basic arithmetic operations like Addition, Subtraction, Multiplication, and Division of two integers.
- NC1 (Nick's Class 1): Tasks that involve Sorting a list of numbers, finding the Maximum Element in an array, and determining the Connected Components of a graph.
- …
- Computational Time Complexity, such as:
- P (Polynomial Time): Tasks that include finding the Shortest Path between two nodes in a graph, determining the Maximum Flow in a network, and checking the satisfiability of a formula in Propositional Logic.
- NP (Nondeterministic Polynomial Time): Tasks that address problems like the Hamiltonian Circuit Problem, the Traveling Salesman Problem, and the Subset Sum Problem.
- EXPTIME (Exponential Time): Tasks that can be addressed by a Deterministic Turing Machine in Exponential Time.
- PLS (Polynomial Local Search): Tasks that are solvable by a Polynomial-Time Local Search Algorithm.
- Computational Space Complexity, such as:
- L (Logspace): Tasks that decide whether a string belongs to a Regular Language and if a graph is Bipartite.
- DSPACE (Deterministic Space): Tasks that can be resolved by a Deterministic Turing Machine using Logarithmic Space.
- NSPACE (Nondeterministic Space): Tasks that can be tackled by a Nondeterministic Turing Machine using Logarithmic Space.
- PSPACE (Polynomial Space): Tasks that are solvable by a Deterministic Turing Machine in Polynomial Space.
- NEXPSPACE (Nondeterministic Exponential Space): Tasks that can be tackled by a Nondeterministic Turing Machine in Exponential Space.
- …
- Counter-Example(s):
- See: Computational Complexity Measure, Computational Complexity Theory, Computational Problem, Turing Machine, Big O Notation, Time Hierarchy Theorem, Space Hierarchy Theorem.
References
2021
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Complexity_class Retrieved:2021-9-1.
- In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers).
The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE (where ⊆ denotes the subset relation). However, many relationships are not yet known; for example, one of the most famous open problems in computer science concerns whether or not P equals NP. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether nondeterminism adds any computational power to computers and whether problems having a solution that can be quickly checked for correctness can also be quickly solved.
- In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
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.
- … 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.
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.
- 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:
2015
- (Wikiversity, 2015) ⇒ https://en.wikiversity.org/wiki/Introduction_to_Complexity_Theory/Time_Complexity Last edited: 18 July 2015.
- QUOTE: The concept of complexity classes helps us group problems according to the way in which the are solved. Complexity classes have a complex and ill-understood relationship amongst each other.
One type of time complexity class is DTIME (sometimes refered to as TIME), a complexity class that describes the computational time of a problem on a deterministic Turing machine. All complexity classes that are based around the concept of time complexity on a deterministic Turing machine may be defined in terms of this class.
Another type of time complexity class is the non-deterministic analogue of DTIME, NTIME. The relationship between these two classes is not fully understood.
- QUOTE: The concept of complexity classes helps us group problems according to the way in which the are solved. Complexity classes have a complex and ill-understood relationship amongst each other.
2006
- (Sipser, 2006) ⇒ Michael Sipser (2006). “Introduction to the Theory of Computation (Second Edition)". In: Thomson - Course Technology. ISBN: 0-534-95097-3
- QUOTE: Let $t: \mathcal{N} \to \mathcal{R^+}$ be a function. Define the time complexity class, TIME(t(n)), to be the collection of all languages that are decidable by an O(t(n)) time Turing machine.
1998
- (Allender et al. , 1998) ⇒ Eric Allender, Michael C. Loui, and Kenneth W. Regan (1998). "Complexity Classes Chapter 27 of the forthcoming CRC Handbook on Algorithms and Theory of Computation".
- QUOTE: Typically, a complexity class is defined by (1) a model of computation, (2) a resource (or collection of resources), and (3) a function known as the complexity bound for each resource.
The models used to define complexity classes fall into two main categories: (a) machine-based models, and (b) circuit-based models. Turing machines (TMs) and random access machines (RAMs) are the two principal families of machine models (...)
We repeat Definition 3.2 of that chapter to define the following fundamental time classes and fundamental space classes, given functions $t(n)$ and $s(n)$
- DTIME ($t(n)$) is the class of languages decided by deterministic Turing machines of time complexity $t(n)$.
- NTIME ($t(n)$) is the class of languages decided by nondeterministic Turing machines of time complexity $t(n)$.
- DSPACE ($s(n)$) is the class of languages decided by deterministic Turing machines of space complexity $s(n)$.
- NSPACE ($s(n)$) is the class of languages decided by nondeterministic Turing machines of space complexity $s(n)$.
- QUOTE: Typically, a complexity class is defined by (1) a model of computation, (2) a resource (or collection of resources), and (3) a function known as the complexity bound for each resource.