3
$\begingroup$

Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?

$\endgroup$
5
$\begingroup$

If any PSPACE-complete problem is proved to be in P, then that proves that P = PSPACE, i.e., every problem in PSPACE can be solved in polynomial time.

Why? Suppose we have a polynomial time algorithm for NFA minimization. Since NFA minimization is PSPACE-complete, any other problem in PSPACE can be solved by reducing the problem to NFA minimization, then applying the polynomial-time algorithm for NFA minimization. The definition of PSPACE-complete ensures that the reduction step will complete in polynomial time, so solving that problem can be done in polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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