Difference between revisions 108480392 and 108480397 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)

The theorem is rather surprising. It implies that majority function can be computed with a family of branching programs of constant width and polynomial size, while intuition might suggest that to achieve polynomial size, one needs 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 permutation ''P'' and sometimes as ''Q'', by right-multiplying permutations in first instruction by <math>\alpha</math>, and in 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.

Assume that for all subcircuits <math>D</math> of <math>C</math> and 5-cycles <math>\alpha</math>, there exists a branching program <math>\alpha</math>-computing <math>C</math>. We will show that for all 5-cycles <math>\alpha</math>, there exists a branching program <math>\alpha</math>-computing <math>C</math>.

* If the circuit outputs <math>x_i</math>, the branching program has one instruction checking <math>x_i</math> and outputting identity or <math>\alpha</math> respectively.
* If the circuit outputs <math>\neg C</math>, where <math>C</math> is a different circuit. Create a branching program <math>\alpha^{-1}</math>-computing <math>C</math>, and multiply output of the program (using lemma 1) by <math>\alpha</math> to get a branching program outputting <math>id</math> or <math>\alpha</math>, i.e. <math>\alpha</math>-computing <math>\neg C</math>.
* If the circuit outputs <math>C \wedge D</math>, join the branching programs that <math>\delta^{-1}</math>-compute D, <math>{\gamma}^{-1} </math>-compute C,<math>\delta</math>-compute D, <math>\gamma</math>-compute C. If one of the circuits outputs 0, the resulting program will be identity; if both circuits output 1, the resulting program will work as <math>\epsilon</math>. In other words, we get a program <math>\epsilon</math>-computing <math>C \wedge D</math>. Because <math>\epsilon</math> and <math>\alpha</math> are two 5-cycles, they are conjugate, and there exists a program <math>\alpha</math>-computing <math>C \wedge D</math>.

The size of the branching program is at most <math>4^d</math>, where ''d'' is the depth of the circuit. If the circuit has logarithmic depth, the branching program has polynomial length.⏎
⏎
==References==
<references/>
* [http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf Greenlaw, Raymond, James Hoover, and Walter Ruzzo. ''Limits To Parallel computation; P-Completeness Theory''. ISBN 0-19-508591-4]
* Heribert Vollmer. ''Introduction to Circuit Complexity -- A Uniform Approach''. ISBN 3-540-64310-9
* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1}} Section 15.3: The class '''NC''', pp.375&ndash;381.
* {{cite book|author = [[Dexter Kozen]] | year = 2006 | title = Theory of Computation | publisher = Springer | isbn = 1-84628-297-7}} Lecture 12: Relation of ''NC'' to Time-Space Classes

{{ComplexityClasses}}

{{DEFAULTSORT:Nc (Complexity)}}
[[Category:Complexity classes]]
[[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)]]