Difference between revisions 108480472 and 108480481 on dewiki

{{unsolved|computer science|Is '''NC''' {{=}} '''P''' ?}}
In [[computational complexity theory|complexity theory]], the class '''NC''' (for "Nick's Class") is the set of [[decision problem]]s decidable in [[polylogarithmic time]] on a [[parallel computing|parallel computer]] with a polynomial number of processors.  In other words, a problem is in '''NC''' if there exist cons(contracted; show full)7;'n'' variables of width ''k'' and length ''m'' consists of a sequence of ''m'' instructions. Each of the instructions is a tuple (''i'', ''p'', ''q'') where ''i'' is the index of variable to check (1 ≤ ''i'' ≤ ''n''), and ''p'' and ''q'' are functions from {1,
  2,  ...,  ''k''} to {1,  2,  ...,  ''k''}. Numbers 1, 2, ..., ''k'' are called states of the branching program. The program initially starts in state 1, and each instruction (''i'', ''p'', ''q'') changes the state from ''x'' to ''p''(''x'') or ''q''(''x''), depending on whether the ''i''-th variable is 0 or 1.

A family of branching programs consists of a branching program with ''n'' variables for each ''n''.

It's easy to show that every language ''L'' on {0,1} can be drecided usingognized by a family of branching programs of width 4 and exponential length, or usingby a family of exponential width and linear length.

Every regular language on {0,1} can be recognized withby a family of branching programs of constant width and linear number of instructions (since a DFA can be converted to a branching program).

'''Barrington's theorem'''<ref>D. A. Barrington. [http://www.cs.umass.edu/~barring/publications/bwbp.pdf Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC<sup>1</sup>]</ref> says that the class of languages recognized withable by a family of branching programs of width 5 and polynomial length is exactly nonuniform NC<sup>1</sup>. The proof uses [[solvable group|nonsolvability]] of symmetric group S<sub>5</sup>.

The theorem is rather surprising. It implies that the majority function can be computed withby a family of branching programs of constant width and polynomial size, while intuition might suggest that to achieve polynomial size, one needs a linear number of states.

===Proof of Barrington's theorem===
A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in NC<sup>1</sup>.

Conversely, suppose a circuit in NC<sup>1</sup> is given. Without loss of generality, assume it uses only AND and NOT gates.

Lemma 1: If there exists a branching program that sometimes works as a permutation ''P'' and sometimes as ''Q'', by right-multiplying permutations in the first instruction by <math>\alpha</math>, and in the last instruction left-multiplying by <math>\beta</math>, we can make a circuit of the same length that behaves as <math>\beta P \alpha</math> or <math>\beta Q \alpha</math>, respectively.

Call a branching program <math>\alpha</math>-computing a circuit <math>C</math> if it works as identity when C's output is 0, and as <math>\alpha</math> when C's output is 1.

As a consequence of lemma 1 and the fact that all cycles of length 5 are conjugate, for any two 5-cycles <math>\alpha, \beta</math>, if there exists a branching program <math>\alpha</math>-computing a circuit ''C'', then there exists a branching program <math>\beta</math>-computing the circuit ''C'', of the same length.

Lemma 2: There exists 5-cycles <math>\gamma, \delta</math> such that their [[commutator]] <math>\gamma \delta \gamma^{-1} \delta^{-1} = \epsilon</math> is a 5-cycle. For example, <math>\gamma = (1 2 3 4 5)</math>, <math>\delta = (1 3 5 4 2)</math>.

We will now prove Barrington's theorem by induction.

(contracted; show full)[[Category:Circuit complexity]]

[[de:NC (Komplexitätsklasse)]]
[[es:NC (clase de complejidad)]]
[[ko:NC (복잡도)]]
[[it:NC (complessità)]]
[[ja:NC (計算複雑性理論)]]
[[vi:NC (độ phức tạp)]]