2
$\begingroup$

I want to verify if I am correct in my interpretation of the $\mathrm{NC}^i$ model.

In this model the input is given to at most $O(n^k)$ processors and each processor takes at most $O(\log^i n)$ time to arrive at a solution.

Can the processors communicate on any intermediate data?

How is the result whether accept or reject announced?

A fine grained problem

So the output of the algorithm can depend on partial results computed on previous processors?

There are $O(n^k)$ processors. So even if each processor computes $1$ bit of intermediate data that is useful for all processors then reading the intermediate results will itself take $\Omega(n^k)$ time then there is no way processors can finish in $O(\log^in)$ time.

So what limitations are there in the length and dependency on intermediate results?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think your description of NC contains mistakes, as I pointed out in comment below the answer of Denis Pankratov. $\endgroup$
    – Thomas Klimpel
    Feb 20, 2016 at 11:34

1 Answer 1

Reset to default
1
$\begingroup$

The model of parallel computing used in the definition of Nick's class is PRAM (see this wiki page, note: particular policy for handling read/write conflicts is irrelevant for Nick's class). In this model, the processors share memory and a common clock, but are otherwise independent. Therefore, any communication that happens between processors uses memory as the channel. The result of the computation can be announced in some pre specified register.

Edit:

Note there are a couple ambiguities in your statements: to show that a problem belongs to $\mathrm{NC}^i$ you can choose $k$ (the power in your polynomial number of processors) depending on the particular problem, while $i$ is fixed. Also, all the quantities should only be specified up to a constant, e.g. $O(\log^i n)$ time and $O(n^k)$ processors.

Improve this answer
$\endgroup$
5
  • $\begingroup$ -1 There is one mistake in the description of NC from the question. The question was to verify whether his understanding is correct, so finding this mistake should at least be part of the first answer to this question, otherwise the impression arises that the description of NC given in the question is correct. $\endgroup$
    – Thomas Klimpel
    Feb 19, 2016 at 23:56
  • $\begingroup$ Is this better? $\endgroup$
    – Denis Pankratov
    Feb 20, 2016 at 0:35
  • $\begingroup$ At least it makes it clear that the description should be improved. I was rather more concerned about not mentioning the total time spend to arrive at a solution, and instead limiting the time each individual processor may spend. $\endgroup$
    – Thomas Klimpel
    Feb 20, 2016 at 9:57
  • $\begingroup$ @DenisPankratov So the output of the algorithm can depend on partial results computed on previous processors? $\endgroup$
    – Turbo
    Feb 21, 2016 at 8:12
  • $\begingroup$ Yes, and time is measured by a common clock. $\endgroup$
    – Denis Pankratov
    Feb 21, 2016 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.