10
$\begingroup$

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors.

I want to know about the exponential analogue, which would cover problems that can be decided in polynomial time using an exponential number of processors.

What I'm looking for is a name for this class and any known relations between this class and other complexity classes, or any canonical problems for the class. It seems straightforward that it would contain NP and co-NP, and i think it is contained within PSPACE, but I'm not sure much else about it.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Time in circuits corresponds to the depth. Therefore by polynomial time means polynomial depth.

The number of processors is the size of the circuit, i.e. number of the gates in the circuit. So by exponential number of processors you allow exponential size. This would be the class $\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$. But every function is already in $\mathsf{DepthSize}(2, 2^{n^{O(1)}})$ (think of the CNF of the function you want to compute).

The take away is that exponential number of processors is too strong to be useful by itself.

One reasonable restriction to put is to limit the amount of communication between different processes. E.g. we each process can only communicate with only polynomially many other processes and the messages have polynomial size. That would be $\mathsf{PSpace}$ as explained in answers to Aterm's question on cstheory. Another way to see it to remember that $\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$, problems computable by alternating Turing machines in polynomial time. Alternation in Turing machines is essentially forking new processes and then joining after they finish by taking the conjunction/disjunction of their return values.

Improve this answer
$\endgroup$
7
  • $\begingroup$ One gets PSPACE even when the only restriction on communication is the time bound. ​ ​ $\endgroup$
    – user12859
    Commented Jan 3, 2016 at 7:30
  • $\begingroup$ @Ricky, it really depends on the model. If the model is alternating Turing machine then yes as I have written in my answer. If it is general circuits (the nonuniform NC circuits) then not so. The time bound for circuits is depth and any function is computable by a depth 2 CNF. $\endgroup$
    – Kaveh
    Commented Jan 3, 2016 at 7:32
  • $\begingroup$ The OP specified the model as parallel machine. ​ ​ $\endgroup$
    – user12859
    Commented Jan 3, 2016 at 7:34
  • $\begingroup$ @Ricky, what do you mean by "parallel machine"? There is many models that try to capture the notion of parallel computation. E.g. take PRAM. OP asks about NC which is a class of circuits and w.r.t. that what I stated holds. $\endgroup$
    – Kaveh
    Commented Jan 3, 2016 at 7:38
  • $\begingroup$ I essentially mean PRAM. ​ The OP says NC "is the class of problems that can be decided in poly-log time using a polynomial number of processors", and asks about "problems that can be decided in polynomial time using an exponential number of processors." ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Jan 3, 2016 at 7:59

Your Answer

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

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