10
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.