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.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
