<p>As Ryan says, this class is PSPACE. This class is often called NC(poly) in the literature. Here is a direct quote from the <a href="http://dx.doi.org/10.1145/1859204.1859231">QIP = PSPACE</a> paper:</p>

<blockquote>
  <p>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(2<sup>poly</sup>) has also previously been used for this class [11].) For decision problems, it is known that NC(poly) = PSPACE [10]. </p>
  
  <p>[10]  A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6:733–
  744, 1977.</p>
  
  <p>[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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2011-05-27T21:11:04.907Z
2011-05-27T21:11:04.907Z
Robin Kothari
<p>I believe the class you are looking for is $PSPACE$. Suppose you have $exp(n^k) = 2^{O(n^k)}$ processors fitting the requirements:</p>

<blockquote>
  <ol>
  <li>Every computer reads the polynomial number of polynomial sized messages it received in  the previous time step.</li>
  <li>Every computer runs some polytime computation that can depend on these messages.</li>
  <li>Every computer passes a message (of polylength) to each of its neighbours.</li>
  </ol>
</blockquote>

<p>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).  </p>

<p>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$.</p>

CC BY-SA 3.0
2011-05-28T04:14:17.150Z
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
CC BY-SA 3.0
2011-05-29T03:49:04.003Z
@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
CC BY-SA 3.0
2011-05-29T09:51:29.920Z
@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
CC BY-SA 3.0
2011-05-30T18:39:57.810Z
@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
CC BY-SA 3.0
2011-05-30T22:49:47.303Z
I think I understand the situation better after reading  your and Robin's comments, thanks.
Kaveh
CC BY-SA 4.0
2021-03-13T09:24:28.100Z
@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
CC BY-SA 4.0
2021-03-13T16:32:40.350Z
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
CC BY-SA 3.0
2011-05-27T08:55:40.880Z
2011-05-27T08:55:40.880Z
Ryan Williams
<p>$\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:</p>

<blockquote>
  <p>$\mathsf{NC}$ is to $\mathsf{P}$ as <em>_</em>_ is to $\mathsf{EXP}$</p>
</blockquote>

<p>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:</p>

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

<p>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?</p>

CC BY-SA 3.0
2011-05-27T04:06:11.767Z
related question, I think: http://cstheory.stackexchange.com/q/2788/1037
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-27T04:32:31.243Z
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
CC BY-SA 3.0
2011-05-27T04:39:38.063Z
the resulting class will contain $EXP$ and the analogy will not hold as $NC \subseteq P$.
Kaveh
CC BY-SA 3.0
2011-05-27T05:08:53.143Z
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
CC BY-SA 3.0
2011-05-27T05:58:23.593Z
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
<cc.complexity-theory><reference-request><complexity-classes><circuit-complexity><dc.parallel-comp>
What is the big version of NC?
Artem Kaznatcheev
# What is the big version of NC?

(Asked by: username_0 on 2011-05-27)

$\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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, circuit-complexity, dc.parallel-comp

> **Comments:**
> **username_0**: related question, I think: http://cstheory.stackexchange.com/q/2788/1037  
> **username_1**: 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)  
> **username_1**: the resulting class will contain $EXP$ and the analogy will not hold as $NC \subseteq P$.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2011-05-27. Score: 28 | Accepted answer

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$.

> **Comments:**
> **username_1**: 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?  
> **username_2**: @username_1: 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.  
> **username_1**: @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.  
> **username_3**: @username_1, 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).  
> **username_1**: I think I understand the situation better after reading  your and Robin's comments, thanks.  
> **username_4**: @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$?  
> **username_3**: If you mean quasipolynomial size... then Yes, this is immediate from the standard reduction from circuits of depth d to formulas of depth d.  

---

### Answer by username_2 on 2011-05-27. Score: 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](http://dx.doi.org/10.1145/1859204.1859231) 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.


---

