en.wikipedia.org/wiki/NC_(complexity)
3 corrections found
every sum between two bits x i and x j is expressible by means of basic logical operators, e.g. through the Boolean expression ( x i ∧ ¬ x j ) ∨ ( ¬ x i ∧ x j )
The displayed formula is XOR, not ordinary addition. XOR is addition modulo 2 without carry, so it does not equal the full sum of two bits.
Full reasoning
The Boolean formula shown,
(x_i ∧ ¬x_j) ∨ (¬x_i ∧ x_j),
is the standard expression for exclusive-or (XOR).
According to NIST, XOR is bitwise addition modulo 2 and is equivalent to binary addition without carry. That means it matches the ordinary sum of two bits only in the cases 0+0=0, 0+1=1, and 1+0=1. It fails on 1+1, because ordinary addition gives 2, while XOR gives 0.
So this formula does not express the full sum of two bits; it expresses only their sum modulo 2 (their parity). A correct description of two-bit addition would need both a sum bit (XOR) and a carry bit.
1 source
- exclusive-OR - Glossary | CSRC
Exclusive-Or (XOR) operator, defined as bit-wise modulo 2 arithmetic with no carry... Equivalent to binary addition without carry.
The problem consists in counting the number of 1s in a string made of 1 and 0.
A parity check does not ask for the full count of 1s. It asks only for the parity of that count—whether the number of 1s is odd or even.
Full reasoning
This sentence conflates parity with counting (the Hamming weight/popcount problem).
A parity computation keeps only the lowest-order bit of the sum of the input bits—equivalently, it determines whether the number of 1s is odd or even. NIST defines a parity bit as a checksum obtained by computing the binary sum of the bits and discarding all but the low-order bit of that sum. That is not the same task as counting the number of 1s exactly.
So the example is describing the wrong problem statement: exact counting returns a value from 0 to n, while parity returns just one bit.
1 source
- parity bit - Glossary | CSRC
A checksum that is computed on a block of bits by computing the binary sum of the individual bits in the block and then discarding all but the low-order bit of the sum.
The size of the branching program is at most 4d, where d is the depth of the circuit.
Barrington’s theorem gives a branching-program length exponential in the circuit depth, not linear in it. The standard bound is at most 4^d, not 4d.
Full reasoning
This bound is incorrect as written.
In Barrington’s theorem, a fan-in-2 Boolean circuit of depth d is converted into a width-5 branching program of length at most 4^d. The construction multiplies the length by 4 at each inductive step, so the resulting size is exponential in the depth, not linear.
That exponential bound is exactly why logarithmic-depth circuits still yield polynomial-length branching programs: if d = O(log n), then 4^d = n^{O(1)}. The sentence's 4d would imply a much smaller linear bound and does not match the theorem.
2 sources
- Computational Complexity: Barrington's Theorem
The theorem is that if you have a boolean circuit C of fan-in two and depth d ... there is a program of length at most 4^d that evaluates to sigma if C evaluates to true and to the identity if C evaluates to false.
- Private Function Evaluation with Cards
For any Boolean circuit C of depth d ... there exists a branching program B = B(C) of width 5 and N ≤ 4^d instructions that computes C.