24

$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$, $k$. My question is if there is an analogous complexity class where time is $n^c$ and number of processors is $2^{n^k}$. As a fill-in-the-blank question:

$\mathsf{NC}$ is to $\mathsf{P}$ as __ is to $\mathsf{EXP}$

In particular, I am interested in a model where we have an exponential number of computers arranged in a network with polynomially bounded degree (lets say the network is independent of the input/problem or atleast somehow easy to construct, or any other reasonable uniformity assumption). At each time step:

  1. Every computer reads the polynomial number of polynomial sized messages it received in the previous time step.
  2. Every computer runs some polytime computation that can depend on these messages.
  3. Every computer passes a message (of polylength) to each of its neighbours.

What is the name of a complexity class corresponding to these sort of models? What is a good place to read about such complexity classes? Are there any complete-problems for such a class?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
  • related question, I think: http://cstheory.stackexchange.com/q/2788/1037 – Artem Kaznatcheev May 27 '11 at 04:06
  • We have

    $NC^k = ASpaceTime(O(\log n), (\log n)^k)$, $NC = ASpaceTime(O(\log n), (\log n)^{O(1)})$, $P = Time(n^{O(1)})$, $EXP = Time(2^{n^{O(1)}})$.

    So the corresponding class to $NC^k$ might be something like $ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$ and then the corresponding class to $NC$ will be $ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$. It is just some algebraic manipulation, I haven't checked if it satisfies your requirements, but I think it will satisfy the three conditions but will not have exponentially many computers. I think you should drop that requirement otherwise(more)

     – Kaveh May 27 '11 at 04:32
  • the resulting class will contain $EXP$ and the analogy will not hold as $NC \subseteq P$. – Kaveh May 27 '11 at 04:39
  • I don't understand where you got $log n$ as the space complexity. As far as I know $NC$ allows polynomially many gates. If we want to go along the lines of your analogue then we should look at $NC$ as $PT/WK(log^c n,n^k)/poly$ and then the complexity class I am looking for is something like $PT/WK(n^c ,2^{n^k})/poly$. However, I was hoping that there is a better characterization that this. – Artem Kaznatcheev May 27 '11 at 05:08
  • That is standard (though it is not in the Complexity Zoo), check e.g. Ruzzo, "On uniform circuit complexity", 1981. Also I think you should work with uniform classes, every function has exponential size alternation/logical depth 2 circuits (and this will satisfy the three conditions if we use bounded fan-in and depth $\log n$). And as I said, if there are exponentially many nodes then the analogy does not hold. Also a main property of parallel computation is saving time, e.g. it is poly-log time in the case of $NC$. I think quasi-polynomial time would correspond to poly-log time. – Kaveh May 27 '11 at 05:58

2 Answers2

28

I believe the class you are looking for is $PSPACE$. Suppose you have $exp(n^k) = 2^{O(n^k)}$ processors fitting the requirements:

  1. Every computer reads the polynomial number of polynomial sized messages it received in the previous time step.
  2. Every computer runs some polytime computation that can depend on these messages.
  3. Every computer passes a message (of polylength) to each of its neighbours.

This can be modeled by having a circuit with $poly(n)$ layers, where each layer has $exp(n^k)$ "gates", and each "gate" does a polynomial time computation (satisfying part 2) with polynomial fan-in (satisfying part 1), and has polynomial fan-out (satisfying part 3).

Since each gate computes a polynomial time function, they each can be replaced by a polynomial size circuit (with AND/OR/NOT) in the usual way. Note the polynomial fan-ins and fan-outs can be made to be 2, by only increasing the depth by a $O(\log n)$ factor. What remains is a $poly(n)$ depth uniform circuit with $exp(n^k)$ AND/OR/NOT gates. This is precisely alternating polynomial time, which is precisely $PSPACE$.

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
  • Ryan, I don't wee how you are putting the exponential number of computers in polynomially many layers, it seem to me that the depth can be exponential, could you explain it a little bit more why this is possible? Also it seems to me that the trivial construction of CNF circuit of a arbitrary given function as a fan-in 2 circuit would satisfy the requirements, am I missing something? – Kaveh May 28 '11 at 04:14
  • 1
    @Kaveh: I don't understand your first question. About the second, although there is an exponential-size depth-2 circuit for any function, NC(poly) requires that you be able to generate the circuits uniformly, so you can't produce arbitrary circuits for each input size. – Robin Kothari May 29 '11 at 03:49
  • @Robin, thanks. Probably I am confusing things. (I feel that the depth of the circuits corresponding to PSpace should be exponential, also I think PSpace is EXP as L is to P so stating the same thing when L is replaced by NC is strange for me, I feel that the class we are looking after should be between PSpace and EXP.) I have to think a little bit more to understand what is going on here. – Kaveh May 29 '11 at 09:51
  • @Kaveh, I assigned the number of layers (i.e. the depth) to be exponential, so the depth cannot be exponential, by definition. There are exponentially many processors, so your CNF will need exponential fan-in, violating one of the conditions. The depth of exponential-size circuits corresponding to PSPACE is polynomial. The reason this is true, and the reason that both analogies are "valid" in a sense ("PSPACE is to EXP as L is to P" and "PSPACE is to EXP as NC is to P") is because PSPACE = Alternating Polynomial Time. We do not know if L = Alternating Logarithmic Time (this is NC1). – Ryan Williams May 30 '11 at 18:39
  • I think I understand the situation better after reading your and Robin's comments, thanks. – Kaveh May 30 '11 at 22:49
  • @RyanWilliams You mention fan-in $2$. Can every $NC^k$ circuit be replaced by $2^{O(\log^kn)}NC^k$ circuit having fan-out $1$? – Turbo Mar 13 '21 at 09:24
  • 1
    If you mean quasipolynomial size... then Yes, this is immediate from the standard reduction from circuits of depth d to formulas of depth d. – Ryan Williams Mar 13 '21 at 16:32
25

As Ryan says, this class is PSPACE. This class is often called NC(poly) in the literature. Here is a direct quote from the QIP = PSPACE paper:

We consider a scaled-up variant of NC, which is the complexity class NC(poly) that consists of all functions computable by polynomial-space uniform families of Boolean circuits having polynomial-depth. (The notation NC(2poly) has also previously been used for this class [11].) For decision problems, it is known that NC(poly) = PSPACE [10].

[10] A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6:733– 744, 1977.

[11] A. Borodin, S. Cook, and N. Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58:113–136, 1983.

One way to see this is to prove both inclusions directly. To see that NC(poly) is in PSPACE, note that we can compute the output of the final gate recursively, and we'll only require a stack of size equal to the depth of the circuit, which is polynomial. To show that PSPACE is in NC(poly), note that QBF, which is PSPACE-complete, can be written as a polynomial depth circuit with exponentially many gates in the usual way -- the exists quantifier is an OR gate, the forall quantifier is an AND gate. Since there are only polynomially many quantifiers, this is a polynomial depth circuit.

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116