2
$\begingroup$

I wondered about the following quote from NC (Wikipedia):

$NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and depth $O(\log^i n)$, or the class of decision problems solvable in time $O(\log^i n)$ on a parallel computer with a polynomial number of processors.

Are these classes actually the same?

Looking at the proofsketch of Lemma 2.4.2 in Limits to Parallel Computation, we have a logarithmic depth overhead when converting from the PRAM model to a circuit. The reason seems to be a uniform cost measure for the PRAMs operations. Hence, I would expect $NC^{i + 1}$ to be the class of decision problems solvable in time $O(\log^i n)$ (uniform cost measure) on a parallel computer with a polynomial number of processors.

If the classes are different, does the additional requirement of a logarithmic cost measure fix this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.