Difference between revisions 108480465 and 108480470 on dewiki

< previous diff
next diff >
Benutzer:Schreiber/NC (complexity)
{{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)

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

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

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

(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)]]