Questions tagged [nc]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
13 views

Is counting the number of occurences in NC¹?

Let $c ∈ ℕ₊$ be constant and $p∈\{0,1\}^c$ a fixed bitpattern of width $c$. Let us assume that the input length is structured as a list of blocks $b_1 … b_n$, each block having width $c$; is it ...
1
vote
2answers
53 views

Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?

Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?
4
votes
1answer
393 views

What is the relation between NC and P/poly?

I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)
0
votes
1answer
62 views

Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size." I think that this may be missing a constraint....