Talk:NC (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics


Should this page mention NC0, too? The page AC0 has a red link NC0; one way to fix it would be to redirect NC0 to NC and write something about NC0 here. The current description in the section "The NC Hierarchy" is actually somewhat misleading, as it suggests that the hierarchy begins from NC1, even though NC0 exists, in the sense that it has a well-defined meaning and it has been used in literature. For the definition of NC0 and further references, see [1]. (However, please note that explaining NC0 is slightly non-trivial: while NCi for i > 0 usually refers to decision problems, NC0 usually refers to functions. Therefore adding NC0 here might add confusion, and a short page devoted to NC0 might be a better solution.) — Miym (talk) 23:16, 10 December 2008 (UTC)

Barrington's theorem[edit]

Needs to be changed: The modelling of branching programs is highly unclear. E.g. what constitutes a state? It contains wrong claims: Every language on 0,1 can be decided (or I do not understand the term language on 0,1) — Preceding unsigned comment added by (talk) 15:00, 16 July 2012 (UTC)

I changed “decided” to “recognized”, since recognizability by a nonuniform family of branching programs does not imply decidability.—Emil J. 14:46, 17 July 2012 (UTC)