<p>It appears that nobody has provided an answer to this question.  One reason may be that it's not clear what you mean by &quot;the rest of the polynomial hierarchy&quot;.  Indeed, it's not clear that P=NC would imply any sort of collapse of PH, but it would certainly imply some consequences regarding the relationship between time, space, and alternations.</p>
<p>One obvious consequence of NC=P is that EXPTIME = PSPACE.  (This follows by a simple padding argument, using the fact that NC is contained in SPACE(polylog(n)).  One can similarly derive other consequences (such as EXPTIME (which is equal to AlternatingSpace(poly(n)) having alternating algorithms that use simulataneously small running time and small space).</p>
<p>...but I'm not sure whether this is the sort of thing you're asking about.</p>

CC BY-SA 4.0
2023-09-12T23:53:35.990Z
2023-09-12T23:53:35.990Z
Eric Allender
<p>If <span class="math-container">$NC=P$</span> (with a constructive polynomial time algorithm that converts any <span class="math-container">$P$</span> time circuit to a <span class="math-container">$NC$</span> circuit), what impact would it have on the rest of the Polynomial Hierarchy?</p>
<p>Couldn't find much in the literature.</p>

<cc.complexity-theory><circuit-complexity><conditional-results>
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
J.Doe
# Does $NC=P$ imply the collapse of Polynomial Hierarchy?

(Asked by: username_0 on 2023-06-19)

If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy?

Couldn't find much in the literature.

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

---

## 1 answers

### Answer by username_1 on 2023-09-12. Score: 8

It appears that nobody has provided an answer to this question. One reason may be that it's not clear what you mean by "the rest of the polynomial hierarchy". Indeed, it's not clear that P=NC would imply any sort of collapse of PH, but it would certainly imply some consequences regarding the relationship between time, space, and alternations.

One obvious consequence of NC=P is that EXPTIME = PSPACE. (This follows by a simple padding argument, using the fact that NC is contained in SPACE(polylog(n)). One can similarly derive other consequences (such as EXPTIME (which is equal to AlternatingSpace(poly(n)) having alternating algorithms that use simulataneously small running time and small space).

...but I'm not sure whether this is the sort of thing you're asking about.


---

