Editing Complexity class (section)

====Important complexity classes====
The complexity class '''[[P/poly]]''' is the set of languages that are decidable by polynomial-size circuit families. It turns out that there is a natural connection between circuit complexity and time complexity. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a Turing machine), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in <math>\mathsf{DTIME}(t(n))</math>, where <math>t</math> is a function <math>t:\mathbb{N} \to \mathbb{N}</math>, then it has circuit complexity <math>O(t^2(n))</math>.{{sfn|Sipser|2006|p=355}} It follows directly from this fact that [[P (complexity)|<math>\mathsf{\color{Blue}P}\subset\textsf{P/poly}</math>]]. In other words, any problem that can be solved in polynomial time by a deterministic Turing machine can also be solved by a polynomial-size circuit family. It is further the case that the inclusion is proper, i.e. <math>\textsf{P}\subsetneq \textsf{P/poly}</math> (for example, there are some [[undecidable problem]]s that are in '''P/poly''').

'''P/poly''' has a number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to [[P versus NP|'''P''' versus '''NP''']]. For example, if there is any language in '''NP''' that is not in '''P/poly''', then <math>\mathsf{P}\neq\mathsf{NP}</math>.{{sfn|Arora|Barak|2009|p=286}} '''P/poly''' is also helpful in investigating properties of the [[polynomial hierarchy]]. For example, if '''[[NP (complexity)|NP]]''' ⊆ '''P/poly''', then '''PH''' collapses to <math>\Sigma_2^{\mathsf P}</math>. A full description of the relations between '''P/poly''' and other complexity classes is available at "[[P/poly#Importance of P/poly|Importance of P/poly]]". '''P/poly''' is also helpful in the general study of the properties of [[Turing machine]]s, as the class can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded [[advice (complexity)|advice function]].

Two subclasses of '''P/poly''' that have interesting properties in their own right are '''[[NC (complexity)|NC]]''' and '''[[AC (complexity)|AC]]'''. These classes are defined not only in terms of their circuit size but also in terms of their '''depth'''. The depth of a circuit is the length of the longest [[directed path]] from an input node to the output node. The class '''NC''' is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having polylogarithmic depth. The class '''AC''' is defined similarly to '''NC''', however gates are allowed to have unbounded fan-in (that is, the AND and OR gates can be applied to more than two bits). '''NC''' is a notable class because it can be equivalently defined as the class of languages that have efficient [[parallel algorithm]]s.