<p>(I've seen Ryan's answer, but I just wanted to provide another perspective, which was too long to fit into a comment.)</p>

<p>In the $L = P \Rightarrow PSPACE = EXP$ proof, all that you need to know about L, informally, is that when blown up by an exponential, L becomes PSPACE.  The same proof goes through for NL, because NL blown up by an exponential also becomes PSPACE.  </p>

<p>Similarly, when NC is blown up by an exponential, you do get PSPACE.  I like to see this in terms of circuits: NC is the class of polynomial size circuits with polylog depth.  When blown up, this becomes exponential size circuits with polynomial depth.  One can show that this is exactly PSPACE, once the appropriate uniformity conditions are added in.  I guess if NC is defined with L-uniformity, then this will get PSPACE-uniformity.</p>

<p>The proof should be easy. In one direction, take a PSPACE-complete problem like TQBF and express the quantifiers using AND and OR gates of exponential size. In the other direction, try traversing the polynomial depth circuit recursively. The stack size will be polynomial, so this can be done in PSPACE.</p>

<p>Finally, I came up with this argument when I saw the question (and before reading Ryan's answer), so there might be bugs. Please point them out.</p>

CC BY-SA 2.5
2010-09-24T19:50:13.897Z
One correction: NC has circuits of polynomial size and polylog depth, but this is still only polynomial depth after translation.
Ryan Williams
CC BY-SA 2.5
2010-09-24T21:10:14.583Z
@Ryan: You're right. I'll fix that.
Robin Kothari
CC BY-SA 2.5
2010-09-24T18:27:44.390Z
2010-09-24T21:10:54.870Z
2010-09-24T21:10:54.870Z
Robin Kothari
<p>Here's a little more detail from the perspective of simulating time-space bounded Alternating Turing machine.</p>

<p>Suppose that $P = NC$.</p>

<p>Since $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$, we get $$P = ATISP((\log(n))^{O(1)}, O(\log(n))).$$</p>

<p>Now, consider the linear time universal simulation problem $LinU$ where we are given an encoding on a Turing machine $M$ and an input string $x$ of length $n$ and we want to know if $M$ accepts $x$ in at most $n$ steps.</p>

<p>We know that $LinU \in P$.  Therefore, there exists a constant $c$ (sufficiently large) such that $$(*) \; LinU \in ATISP(\log^c(n), c\log(n)).$$</p>

<p>As a result of a padding argument (a little tricky see comments), we have $$(1) \; DTIME(n) \subseteq ATISP(\log^c(n), c\log(n)).$$</p>

<p>Extending the padding argument, we get
$$(2) \; DTIME(n^k) \subseteq ATISP(k^c\log^c(n), kc\log(n)).$$
$$(3) \; DTIME(2^{n^k}) \subseteq ATISP(k^cn^{kc}, kcn^{k}).$$</p>

<p>Further, there are known results about the simulation of Alternating time-space bounded Turing machines.  In particular, we know that $$ATISP(\log^c(n), c\log(n)) \subseteq DSPACE(O(\log^{c+1}(n))).$$</p>

<p>Therefore, we (essentially) have the following for all natural numbers $k$:</p>

<p>$$(2^{*}) \; DTIME(n^k) \subseteq DSPACE(k^{c+1}\log^{c+1}(n))$$
$$(3^{*}) \; DTIME(2^{n^k}) \subseteq DSPACE(n^{k(c+1)}).$$</p>

<p>From $(3^{*})$, we would get that $EXP = PSPACE$.</p>

<p>====================After Thought===================</p>

<p>It is important to notice that $P = NC$ implies $$ATISP((\log(n))^{O(1)}, O(\log(n))) = ATISP(\log^c(n), O(\log(n)))$$ for some constant $c$.</p>

<p>Any comments or corrections are welcomed.  :)</p>

CC BY-SA 3.0
2014-11-19T05:05:43.640Z
The mistake is in the step that you move from LinU to LinTime: you ignore the overhead caused by reductions to LinU from LinTime machines. Just because a universal machine for the class C is in class C' doesn't mean C is a subset of C'.
Kaveh
CC BY-SA 3.0
2014-11-19T06:42:05.027Z
Hi Kaveh, thank you for the response.  First let me describe the issue, then I'll try to clear it up.  Now, say we are given a $2n$ time bounded TM $M$.  Let's reduce $L(M)$ to $LinU$.  Let $x$ be given.  We can't just check if $(M,x)$ is in $LinU$.  We have to modify $M$ slightly to obtain $M'$ and pad $x$ with $n$ characters to obtain $x'$ which has $2n$ characters in total.  Then, we check if $(M',x')$ is in $LinU$.  For the reduction, we map $x$ to $(M',x')$.  We should be able to do this in linear time, but wait we need it to be done in $\log^c(n)$ time.
Michael Wehar
CC BY-SA 3.0
2014-11-19T06:47:48.703Z
Now, I'll propose a way to clear it up, but honestly, your input is appreciated because there is still more for me to learn on models of alternating machines with random access tapes.
Michael Wehar
CC BY-SA 3.0
2014-11-19T06:55:14.020Z
Some alternating machine $A$ can solve $LinU$ in $\log^c(n)$ time.  Rather than computing a many one reduction like I described, let's just build a machine $A'$ that simulates $A$ on input $(M',x')$.  Since $M'$ is fixed, it can be hard coded into $A'$ with no problems.  The input for $A'$ will be $x$, but we need quick access to $x'$ which is $x$ with a length $n$ padding of say 0's.
Michael Wehar
CC BY-SA 3.0
2014-11-19T06:56:04.763Z
So let's use random access to compute $n$ in binary using a form of binary search.  This should take $\log^2(n)$ time.  Now, $A'$ runs similar to $A$, but anytime that $A$ would use random access, $A'$ first compares the look-up address to $n$ (which was written in binary) to decide whether the character at that address is in $x$, the padding, or a blank symbol.  This should blow-up the runtime by a $c\log(n)$ factor.  Generalizing this construction appears to make (2) still work out (at least with just an extra log factor and larger constants).  I'll review it again soon to make sure.
Michael Wehar
CC BY-SA 3.0
2014-11-19T17:28:57.743Z
Let me simplify the argument: CV is complete for P w.r.t. AC^0 reductions. If P=NC then NC collapses to some NC^i since they are closed under AC^0 reductions.
Kaveh
CC BY-SA 3.0
2014-11-22T22:10:55.057Z
Hi Kaveh, did I clear up the 'mistake'? It appears to work fine to me, but you expressed some doubt and your opinion is valued.
Michael Wehar
CC BY-SA 3.0
2014-11-23T01:01:38.160Z
I didn't finish reading your comments, I started but then I felt it is unnecessarily complicated and stopped reading. It can be fixed probably, but it seems like a long detour. As I wrote, the "after thought", which most of your post is devoted to proving if I understand correctly, is kind of obvious if you notice that the right-hand side is just NC^i: it is like PH=PSpace implying PH collapses. (I kind of fail to see how your answer helps in understanding what Ryan and Robin wrote.)
Kaveh
CC BY-SA 3.0
2014-11-23T06:24:09.183Z
I intended to provide some more detail on what happens if NC=P.  I've been thinking a bit about time-space trade-offs for alternating Turing machines so that influenced my perspective and was why I wrote the after thought.  The comments were intended to give supplemental detail on the padding and help remedy any mistake.  Thank you again, I appreciate the reply.
Michael Wehar
CC BY-SA 3.0
2018-04-29T14:15:31.733Z
@MichaelWehar Do we know $NC^k\subsetneq PSPACE$ at any fixed $k$? In particular do we know $NC^2\subsetneq PSPACE$ and therefore $NC\neq PSPACE$?
Turbo
CC BY-SA 3.0
2018-04-29T22:08:18.447Z
@Turbo Thank you for the comment!!  Correct me if I'm wrong, but it seems that we have $$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$$ and by applying a variation of the time hierarchy theorem along with the relationship between alternating time and deterministic space we have, $$ATIME(n) \subsetneq PSPACE.$$  By combining these two statements, we get $$NC = ATISP((\log(n))^{O(1)}, O(\log(n))) \subseteq ATIME(n) \subsetneq PSPACE.$$
Michael Wehar
CC BY-SA 3.0
2018-04-29T23:49:16.987Z
@MichaelWehar I do not know but I have never seen anywhere that $NC\neq PSPACE$. In fact a comment in https://cstheory.stackexchange.com/questions/39046/complexity-class-equalities-on-the-edge-of-inconsistency says $P-uniform NC^1=PSPACE$ is possible. I have posted a clarification query in https://cstheory.stackexchange.com/questions/40689/from-p-ch-to-p-pspace. Do you think you can take a look?
Turbo
CC BY-SA 3.0
2018-04-30T16:46:55.857Z
@Turbo Thank you very much for the kind reply!!  It may depend on the kind of uniform.  For example, $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ might only hold for Logspace-uniform NC.  Let me think about it and get back to you.  :)
Michael Wehar
CC BY-SA 3.0
2018-05-01T15:44:16.627Z
@Turbo I took a closer look at this paper: https://www.sciencedirect.com/science/article/pii/0022000081900386
Michael Wehar
CC BY-SA 3.0
2018-05-01T15:48:37.673Z
@Turbo Their first notion of uniform requires that the space used for constructing the circuits be bounded.  For their notion of uniform $NC^k$, the space would be bounded by $log^k(n)$.  Using this notion of uniform, they prove that uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$.
Michael Wehar
CC BY-SA 3.0
2018-05-01T15:49:55.893Z
@Turbo As a result of my argument above, we have that their uniform $NC \subsetneq PSPACE$.  However, $P$-uniform $NC$ is different from their uniform $NC$.  As a result, it could still be the case that $P$-uniform $NC = PSPACE$.
Michael Wehar
CC BY-SA 4.0
2018-05-02T01:42:11.097Z
@MichaelWehar Sorry what is the difference between uniform $NC$ and $P$-uniform $NC$ and why is $PSPACE\neq NC$ absent in https://en.wikipedia.org/wiki/NC_(complexity)? So we know $NC\subsetneq PSPACE\subseteq EXP$?
Turbo
CC BY-SA 4.0
2018-05-02T02:07:01.520Z
@Turbo Thank you for the follow-up!!  I really think you should read the definition at the bottom of page 370 from: https://www.sciencedirect.com/science/article/pii/0022000081900386
Michael Wehar
CC BY-SA 4.0
2018-05-02T03:18:16.783Z
@Turbo This definition describes the notion of $U_B$-uniform circuits.  We have $U_B$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$, but we don't know if $P$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$.  As a result, we have $U_B$-uniform $NC$ is a strict subset of $PSPACE$, but it is still not known if $P$-uniform $NC$ is a strict subset of $PSPACE$.  Does that make sense?  Please let me know if you have any further questions.  Hope that you have a nice evening!!  :)
Michael Wehar
CC BY-SA 4.0
2018-05-02T06:26:04.990Z
@MichaelWehar 1. Why is your proof $U_B$ uniform is proper subset of $PSPACE$ and what would your proof need to improve this to $U_{BC}$ uniform and $P$-uniform are proper subset of $PSPACE$?
Turbo
CC BY-SA 4.0
2018-05-02T06:29:01.440Z
2. Where is $U_{BC}$ uniform? Is it also not known to be proper subset of $PSPACE$ like $P$-uniform? Is $U_B$-uniform in $U_{BC}$-uniform in $P$_uniform?
Turbo
CC BY-SA 4.0
2018-05-02T06:29:06.883Z
3. When wiki or we regular talk about $NC$ do they or we talk about $P$, $U_B$ or $U_{BC}$ uniform?
Turbo
CC BY-SA 4.0
2018-05-02T06:30:49.090Z
4. What is the largest known $X$ such that $X$-uniform $NC$ is proper subset of $PSPACE$?
Turbo
CC BY-SA 4.0
2018-05-02T06:39:10.417Z
5. What is the $NC^1$ versus $TC^0$ problem. Is it open for $U_B$, $U_{BC}$ and $P$ uniform NC?
Turbo
CC BY-SA 4.0
2018-05-03T17:06:54.273Z
@Turbo Thanks for all of your follow-ups!!  I highly recommend that you read the paper that I linked because in it, it says that most of these notions of uniform $NC$ are equivalent.  The paper however does not consider $P$-uniform $NC$ which could possibly be different as I have no way of proving that it is the same.
Michael Wehar
CC BY-SA 4.0
2018-05-03T17:09:58.240Z
@Turbo The reason that the proof I suggested works is because the paper establishes that $U_B$-uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ and for that matter all of the other notions of uniform $NC$ from the paper satisfy this as well.  However, $P$-uniform $NC$ might not satisfy this because it's not known if $P \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$ meaning that we can't simulate the part where we compute the circuits.
Michael Wehar
CC BY-SA 4.0
2018-05-03T17:10:55.390Z
@Turbo I find this back and forth to be rather exhausting.  Why don't we just setup a time to chat over the phone or Skype instead.  That way we can resolve any concerns that you might have.  Thanks again and I hope that you have a great day!!  :)
Michael Wehar
CC BY-SA 4.0
2018-05-03T17:15:05.273Z
@Turbo Question (3) might suggest for a good StackExchange question.  I don't know what is the commonly accepted version of the $NC$ complexity class.
Michael Wehar
CC BY-SA 3.0
2014-11-19T01:35:41.450Z
2014-11-23T06:28:19.773Z
2014-11-23T06:28:19.773Z
Michael Wehar
<p>Yes. $NC$ can be seen as the class of languages recognized by alternating Turing machines that use $O(\log n)$ space and $(\log n)^{O(1)}$ time. (This was first proved by Ruzzo.) $P$ is the class where alternating Turing machines use $O(\log n)$ space but can take up to $n^{O(1)}$ time. For brevity let's call these classes $ATISP[(\log n)^{O(1)},\log n] = NC$ and $ASPACE[O(\log n)] = P$. </p>

<p>Suppose the two classes are equal. Replacing the $n$ with $2^n$ in the above (i.e., applying standard translation lemmas), one obtains </p>

<p>$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$. </p>

<p>If $TIME[2^{O(n)}] \subseteq PSPACE$ then $EXP = PSPACE$ as well, since there are $EXP$-complete languages in $TIME[2^{O(n)}]$.</p>

<p><strong>Edit:</strong> Although the above answer is perhaps more educational, here's a simpler argument: <em>$EXP = PSPACE$ already follows from "$P$ is contained in polylog space" and standard translation.</em> Note "$P$ is contained in polylog space" is a much weaker hypothesis than $NC = P$. </p>

<p>More details: Since $NC$ circuit families have depth $(\log n)^c$ for some constant, every such circuit family can be evaluated in $O((\log n)^c)$ space. Hence $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. So $P = NC$ implies $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$. Applying translation (replacing $n$ with $2^n$) implies $TIME[2^{O(n)}] \subseteq PSPACE$. The existence of an $EXP$-complete language in $TIME[2^{O(n)}]$ finishes the argument.</p>

<p><strong>Update:</strong> Addressing Andreas' additional question, I believe it should be possible to prove something like: $EXP=PSPACE$ iff for all $c$, every polynomially sparse language in $n^{O(\log^c n)}$ time is solvable in polylog space. (Being polynomially sparse means that there are at most $poly(n)$ strings of length $n$ in the language, for all $n$.) If true, the proof would probably go along the lines of Hartmanis, Immerman, and Sewelson's proof that $NE = E$ iff every polynomially sparse language in $NP$ is contained in $P$. (Note, $n^{O(\log^c n)}$ time in polylog space is still enough to imply $PSPACE=EXP$.)</p>

CC BY-SA 4.0
2023-08-18T20:58:11.330Z
@RyanWilliams Can P be described by fan-in 2 circuits of poly(n) depth?
Turbo
CC BY-SA 2.5
2010-09-24T18:24:48.183Z
Thanks for the nice answer.  Dexter Kozen's _Theory of Computation_ has a nice "uniform" notation for Ruzzo's classes on page 69: $STA(f,g,h)$ where $f$ bounds space, $g$ bounds time, and $h$ bounds alternations.  Then $\text{NC} = STA(\log n, {*}, (\log n)^{O(1)})$ while $\text{P} = STA(\log n, {*}, {*})$ which really highlights the construction.
András Salamon
CC BY-SA 2.5
2010-09-24T19:37:30.813Z
Note that I am saying $NC = STA(\log n, (\log n)^{O(1)}, *)$ in the above. However I think these are the same. A machine which takes polynomial time and $O(\log n)$ space but makes only $(\log n)^{O(1)}$ alternations can be turned into another alternating machine which takes only $(\log n)^{O(1)}$ time and $O(\log n)$ space. (The other direction is obvious.) The idea is to insert more alternations so that each polynomial time existential phase and universal phase is "sped up" to run in only $(\log n)^{O(1)}$ time and $O(\log n)$ space, along the lines of Savitch's theorem.
Ryan Williams
CC BY-SA 2.5
2010-09-25T18:01:57.347Z
what we need is some kind of greasemonkey script that automatically links something like "\NP" to the entry in the zoo.
Suresh Venkat
CC BY-SA 2.5
2010-09-24T18:03:24.170Z
2010-09-25T21:47:42.167Z
2010-09-25T21:47:42.167Z
Ryan Williams
<p>The Complexity Zoo points out in the entry on <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:E#exp" rel="noreferrer">EXP</a> that if <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l" rel="noreferrer">L</a> = <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#p" rel="noreferrer">P</a> then <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pspace" rel="noreferrer">PSPACE</a> = EXP.  Since <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npspace" rel="noreferrer">NPSPACE</a> = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that <span class="math-container">$$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$$</span>  We also know that L <span class="math-container">$\subseteq$</span> <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nl" rel="noreferrer">NL</a> <span class="math-container">$\subseteq$</span> <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc" rel="noreferrer">NC</a> <span class="math-container">$\subseteq$</span> P via Ruzzo's resource-bounded alternating hierarchy.</p>
<blockquote>
<p>If NC = P, does it follow that PSPACE = EXP?</p>
</blockquote>
<p>A different interpretation of the question, in the spirit of Richard Lipton: is it more likely that some problems in P cannot be parallelized, than that no exponential-time procedure requires more than polynomial space?</p>
<p>I would also be interested in other &quot;surprising&quot; consequences of NC = P (the more unlikely the better).</p>
<p><strong>Edit:</strong> Ryan's answer leads to a further question: what is the weakest hypothesis that is known to guarantee PSPACE = EXP?</p>
<ul>
<li>W. Savitch. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.</li>
<li>W. L. Ruzzo. On uniform circuit complexity, Journal of Computer and System Sciences 22(3):365-383, 1971.</li>
</ul>
<p><strong>Edit (2014):</strong> updated old Zoo link and added links for all other classes.</p>

CC BY-SA 3.0
2017-12-20T20:43:16.903Z
@Andras: One other consequence which maybe you already know, but hasn't been mentioned yet, is that then the $\mathsf{NC}$ hierarchy would collapse, since $\mathsf{P}$ has complete problems under $\mathsf{L}$-reductions.
Joshua Grochow
CC BY-SA 2.5
2010-09-24T22:24:41.657Z
As I'm sure I'm not the only one to not know what NC is, here's a link: http://en.wikipedia.org/wiki/NC_%28complexity%29
Emil
<cc.complexity-theory><conditional-results>
NC = P consequences?
András Salamon
# NC = P consequences?

(Asked by: username_0 on 2010-09-24)

The Complexity Zoo points out in the entry on [EXP](http://qwiki.stanford.edu/wiki/Complexity_Zoo:E#exp) that if [L](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l) = [P](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#p) then [PSPACE](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pspace) = EXP. Since [NPSPACE](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npspace) = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that $$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$$ We also know that L $\subseteq$ [NL](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nl) $\subseteq$ [NC](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc) $\subseteq$ P via Ruzzo's resource-bounded alternating hierarchy.

> If NC = P, does it follow that PSPACE = EXP?

A different interpretation of the question, in the spirit of Richard Lipton: is it more likely that some problems in P cannot be parallelized, than that no exponential-time procedure requires more than polynomial space?

I would also be interested in other "surprising" consequences of NC = P (the more unlikely the better).

**Edit:** Ryan's answer leads to a further question: what is the weakest hypothesis that is known to guarantee PSPACE = EXP?

* W. Savitch. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.
* W. L. Ruzzo. On uniform circuit complexity, Journal of Computer and System Sciences 22(3):365-383, 1971.

**Edit (2014):** updated old Zoo link and added links for all other classes.

**Tags:** cc.complexity-theory, conditional-results

> **Comments:**
> **username_2**: As I'm sure I'm not the only one to not know what NC is, here's a link: http://en.wikipedia.org/wiki/NC_%28complexity%29  
> **username_1**: @Andras: One other consequence which maybe you already know, but hasn't been mentioned yet, is that then the $\mathsf{NC}$ hierarchy would collapse, since $\mathsf{P}$ has complete problems under $\mathsf{L}$-reductions.  

---

## 3 answers

### Answer by username_4 on 2010-09-24. Score: 29 | Accepted answer

Yes. $NC$ can be seen as the class of languages recognized by alternating Turing machines that use $O(\log n)$ space and $(\log n)^{O(1)}$ time. (This was first proved by Ruzzo.) $P$ is the class where alternating Turing machines use $O(\log n)$ space but can take up to $n^{O(1)}$ time. For brevity let's call these classes $ATISP[(\log n)^{O(1)},\log n] = NC$ and $ASPACE[O(\log n)] = P$.

Suppose the two classes are equal. Replacing the $n$ with $2^n$ in the above (i.e., applying standard translation lemmas), one obtains

$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$.

If $TIME[2^{O(n)}] \subseteq PSPACE$ then $EXP = PSPACE$ as well, since there are $EXP$-complete languages in $TIME[2^{O(n)}]$.

**Edit:** Although the above answer is perhaps more educational, here's a simpler argument: *$EXP = PSPACE$ already follows from "$P$ is contained in polylog space" and standard translation.* Note "$P$ is contained in polylog space" is a much weaker hypothesis than $NC = P$.

More details: Since $NC$ circuit families have depth $(\log n)^c$ for some constant, every such circuit family can be evaluated in $O((\log n)^c)$ space. Hence $NC \subseteq \bigcup\_{c > 0} SPACE[(\log n)^c]$. So $P = NC$ implies $P \subseteq \bigcup\_{c > 0} SPACE[(\log n)^c]$. Applying translation (replacing $n$ with $2^n$) implies $TIME[2^{O(n)}] \subseteq PSPACE$. The existence of an $EXP$-complete language in $TIME[2^{O(n)}]$ finishes the argument.

**Update:** Addressing Andreas' additional question, I believe it should be possible to prove something like: $EXP=PSPACE$ iff for all $c$, every polynomially sparse language in $n^{O(\log^c n)}$ time is solvable in polylog space. (Being polynomially sparse means that there are at most $poly(n)$ strings of length $n$ in the language, for all $n$.) If true, the proof would probably go along the lines of Hartmanis, Immerman, and Sewelson's proof that $NE = E$ iff every polynomially sparse language in $NP$ is contained in $P$. (Note, $n^{O(\log^c n)}$ time in polylog space is still enough to imply $PSPACE=EXP$.)

> **Comments:**
> **username_0**: Thanks for the nice answer.  Dexter Kozen's _Theory of Computation_ has a nice "uniform" notation for Ruzzo's classes on page 69: $STA(f,g,h)$ where $f$ bounds space, $g$ bounds time, and $h$ bounds alternations.  Then $\text{NC} = STA(\log n, {*}, (\log n)^{O(1)})$ while $\text{P} = STA(\log n, {*}, {*})$ which really highlights the construction.  
> **username_4**: Note that I am saying $NC = STA(\log n, (\log n)^{O(1)}, *)$ in the above. However I think these are the same. A machine which takes polynomial time and $O(\log n)$ space but makes only $(\log n)^{O(1)}$ alternations can be turned into another alternating machine which takes only $(\log n)^{O(1)}$ time and $O(\log n)$ space. (The other direction is obvious.) The idea is to insert more alternations so that each polynomial time existential phase and universal phase is "sped up" to run in only $(\log n)^{O(1)}$ time and $O(\log n)$ space, along the lines of Savitch's theorem.  
> **username_8**: what we need is some kind of greasemonkey script that automatically links something like "\NP" to the entry in the zoo.  
> **username_7**: @RyanWilliams Can P be described by fan-in 2 circuits of poly(n) depth?  

---

### Answer by username_3 on 2010-09-24. Score: 13

(I've seen Ryan's answer, but I just wanted to provide another perspective, which was too long to fit into a comment.)

In the $L = P \Rightarrow PSPACE = EXP$ proof, all that you need to know about L, informally, is that when blown up by an exponential, L becomes PSPACE. The same proof goes through for NL, because NL blown up by an exponential also becomes PSPACE.

Similarly, when NC is blown up by an exponential, you do get PSPACE. I like to see this in terms of circuits: NC is the class of polynomial size circuits with polylog depth. When blown up, this becomes exponential size circuits with polynomial depth. One can show that this is exactly PSPACE, once the appropriate uniformity conditions are added in. I guess if NC is defined with L-uniformity, then this will get PSPACE-uniformity.

The proof should be easy. In one direction, take a PSPACE-complete problem like TQBF and express the quantifiers using AND and OR gates of exponential size. In the other direction, try traversing the polynomial depth circuit recursively. The stack size will be polynomial, so this can be done in PSPACE.

Finally, I came up with this argument when I saw the question (and before reading Ryan's answer), so there might be bugs. Please point them out.

> **Comments:**
> **username_4**: One correction: NC has circuits of polynomial size and polylog depth, but this is still only polynomial depth after translation.  
> **username_3**: @Ryan: You're right. I'll fix that.  

---

### Answer by username_5 on 2014-11-19. Score: 3

Here's a little more detail from the perspective of simulating time-space bounded Alternating Turing machine.

Suppose that $P = NC$.

Since $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$, we get $$P = ATISP((\log(n))^{O(1)}, O(\log(n))).$$

Now, consider the linear time universal simulation problem $LinU$ where we are given an encoding on a Turing machine $M$ and an input string $x$ of length $n$ and we want to know if $M$ accepts $x$ in at most $n$ steps.

We know that $LinU \in P$. Therefore, there exists a constant $c$ (sufficiently large) such that $$(\*) \; LinU \in ATISP(\log^c(n), c\log(n)).$$

As a result of a padding argument (a little tricky see comments), we have $$(1) \; DTIME(n) \subseteq ATISP(\log^c(n), c\log(n)).$$

Extending the padding argument, we get
$$(2) \; DTIME(n^k) \subseteq ATISP(k^c\log^c(n), kc\log(n)).$$
$$(3) \; DTIME(2^{n^k}) \subseteq ATISP(k^cn^{kc}, kcn^{k}).$$

Further, there are known results about the simulation of Alternating time-space bounded Turing machines. In particular, we know that $$ATISP(\log^c(n), c\log(n)) \subseteq DSPACE(O(\log^{c+1}(n))).$$

Therefore, we (essentially) have the following for all natural numbers $k$:

$$(2^{\*}) \; DTIME(n^k) \subseteq DSPACE(k^{c+1}\log^{c+1}(n))$$
$$(3^{\*}) \; DTIME(2^{n^k}) \subseteq DSPACE(n^{k(c+1)}).$$

From $(3^{\*})$, we would get that $EXP = PSPACE$.

====================After Thought===================

It is important to notice that $P = NC$ implies $$ATISP((\log(n))^{O(1)}, O(\log(n))) = ATISP(\log^c(n), O(\log(n)))$$ for some constant $c$.

Any comments or corrections are welcomed. :)

> **Comments:**
> **username_6**: The mistake is in the step that you move from LinU to LinTime: you ignore the overhead caused by reductions to LinU from LinTime machines. Just because a universal machine for the class C is in class C' doesn't mean C is a subset of C'.  
> **username_5**: Hi username_6, thank you for the response.  First let me describe the issue, then I'll try to clear it up.  Now, say we are given a $2n$ time bounded TM $M$.  Let's reduce $L(M)$ to $LinU$.  Let $x$ be given.  We can't just check if $(M,x)$ is in $LinU$.  We have to modify $M$ slightly to obtain $M'$ and pad $x$ with $n$ characters to obtain $x'$ which has $2n$ characters in total.  Then, we check if $(M',x')$ is in $LinU$.  For the reduction, we map $x$ to $(M',x')$.  We should be able to do this in linear time, but wait we need it to be done in $\log^c(n)$ time.  
> **username_5**: Now, I'll propose a way to clear it up, but honestly, your input is appreciated because there is still more for me to learn on models of alternating machines with random access tapes.  
> **username_5**: Some alternating machine $A$ can solve $LinU$ in $\log^c(n)$ time.  Rather than computing a many one reduction like I described, let's just build a machine $A'$ that simulates $A$ on input $(M',x')$.  Since $M'$ is fixed, it can be hard coded into $A'$ with no problems.  The input for $A'$ will be $x$, but we need quick access to $x'$ which is $x$ with a length $n$ padding of say 0's.  
> **username_5**: So let's use random access to compute $n$ in binary using a form of binary search.  This should take $\log^2(n)$ time.  Now, $A'$ runs similar to $A$, but anytime that $A$ would use random access, $A'$ first compares the look-up address to $n$ (which was written in binary) to decide whether the character at that address is in $x$, the padding, or a blank symbol.  This should blow-up the runtime by a $c\log(n)$ factor.  Generalizing this construction appears to make (2) still work out (at least with just an extra log factor and larger constants).  I'll review it again soon to make sure.  
> **username_6**: Let me simplify the argument: CV is complete for P w.r.t. AC^0 reductions. If P=NC then NC collapses to some NC^i since they are closed under AC^0 reductions.  
> **username_5**: Hi username_6, did I clear up the 'mistake'? It appears to work fine to me, but you expressed some doubt and your opinion is valued.  
> **username_6**: I didn't finish reading your comments, I started but then I felt it is unnecessarily complicated and stopped reading. It can be fixed probably, but it seems like a long detour. As I wrote, the "after thought", which most of your post is devoted to proving if I understand correctly, is kind of obvious if you notice that the right-hand side is just NC^i: it is like PH=PSpace implying PH collapses. (I kind of fail to see how your answer helps in understanding what Ryan and Robin wrote.)  
> **username_5**: I intended to provide some more detail on what happens if NC=P.  I've been thinking a bit about time-space trade-offs for alternating Turing machines so that influenced my perspective and was why I wrote the after thought.  The comments were intended to give supplemental detail on the padding and help remedy any mistake.  Thank you again, I appreciate the reply.  
> **username_7**: @MichaelWehar Do we know $NC^k\subsetneq PSPACE$ at any fixed $k$? In particular do we know $NC^2\subsetneq PSPACE$ and therefore $NC\neq PSPACE$?  
> **username_5**: @username_7 Thank you for the comment!!  Correct me if I'm wrong, but it seems that we have $$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$$ and by applying a variation of the time hierarchy theorem along with the relationship between alternating time and deterministic space we have, $$ATIME(n) \subsetneq PSPACE.$$  By combining these two statements, we get $$NC = ATISP((\log(n))^{O(1)}, O(\log(n))) \subseteq ATIME(n) \subsetneq PSPACE.$$  
> **username_7**: @MichaelWehar I do not know but I have never seen anywhere that $NC\neq PSPACE$. In fact a comment in https://cstheory.stackexchange.com/questions/39046/complexity-class-equalities-on-the-edge-of-inconsistency says $P-uniform NC^1=PSPACE$ is possible. I have posted a clarification query in https://cstheory.stackexchange.com/questions/40689/from-p-ch-to-p-pspace. Do you think you can take a look?  
> **username_5**: @username_7 Thank you very much for the kind reply!!  It may depend on the kind of uniform.  For example, $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ might only hold for Logspace-uniform NC.  Let me think about it and get back to you.  :)  
> **username_5**: @username_7 I took a closer look at this paper: https://www.sciencedirect.com/science/article/pii/0022000081900386  
> **username_5**: @username_7 Their first notion of uniform requires that the space used for constructing the circuits be bounded.  For their notion of uniform $NC^k$, the space would be bounded by $log^k(n)$.  Using this notion of uniform, they prove that uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$.  
> **username_5**: @username_7 As a result of my argument above, we have that their uniform $NC \subsetneq PSPACE$.  However, $P$-uniform $NC$ is different from their uniform $NC$.  As a result, it could still be the case that $P$-uniform $NC = PSPACE$.  
> **username_7**: @MichaelWehar Sorry what is the difference between uniform $NC$ and $P$-uniform $NC$ and why is $PSPACE\neq NC$ absent in https://en.wikipedia.org/wiki/NC_(complexity)? So we know $NC\subsetneq PSPACE\subseteq EXP$?  
> **username_5**: @username_7 Thank you for the follow-up!!  I really think you should read the definition at the bottom of page 370 from: https://www.sciencedirect.com/science/article/pii/0022000081900386  
> **username_5**: @username_7 This definition describes the notion of $U_B$-uniform circuits.  We have $U_B$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$, but we don't know if $P$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$.  As a result, we have $U_B$-uniform $NC$ is a strict subset of $PSPACE$, but it is still not known if $P$-uniform $NC$ is a strict subset of $PSPACE$.  Does that make sense?  Please let me know if you have any further questions.  Hope that you have a nice evening!!  :)  
> **username_7**: @MichaelWehar 1. Why is your proof $U_B$ uniform is proper subset of $PSPACE$ and what would your proof need to improve this to $U_{BC}$ uniform and $P$-uniform are proper subset of $PSPACE$?  
> **username_7**: 2. Where is $U_{BC}$ uniform? Is it also not known to be proper subset of $PSPACE$ like $P$-uniform? Is $U_B$-uniform in $U_{BC}$-uniform in $P$_uniform?  
> **username_7**: 3. When wiki or we regular talk about $NC$ do they or we talk about $P$, $U_B$ or $U_{BC}$ uniform?  
> **username_7**: 4. What is the largest known $X$ such that $X$-uniform $NC$ is proper subset of $PSPACE$?  
> **username_7**: 5. What is the $NC^1$ versus $TC^0$ problem. Is it open for $U_B$, $U_{BC}$ and $P$ uniform NC?  
> **username_5**: @username_7 Thanks for all of your follow-ups!!  I highly recommend that you read the paper that I linked because in it, it says that most of these notions of uniform $NC$ are equivalent.  The paper however does not consider $P$-uniform $NC$ which could possibly be different as I have no way of proving that it is the same.  
> **username_5**: @username_7 The reason that the proof I suggested works is because the paper establishes that $U_B$-uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ and for that matter all of the other notions of uniform $NC$ from the paper satisfy this as well.  However, $P$-uniform $NC$ might not satisfy this because it's not known if $P \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$ meaning that we can't simulate the part where we compute the circuits.  
> **username_5**: @username_7 I find this back and forth to be rather exhausting.  Why don't we just setup a time to chat over the phone or Skype instead.  That way we can resolve any concerns that you might have.  Thanks again and I hope that you have a great day!!  :)  
> **username_5**: @username_7 Question (3) might suggest for a good StackExchange question.  I don't know what is the commonly accepted version of the $NC$ complexity class.  

---

