Talk:NC (complexity)

NC0?

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

Barrington's theorem

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 163.1.88.5 (talk) 15:00, 16 July 2012 (UTC)[reply]

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)[reply]