patternMinor
What if there is a polynomial-time algorithm to minimize NFA?
Viewed 0 times
minimizenfawhatpolynomialtimealgorithmthere
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#74678, answer score: 5
Revisions (0)
No revisions yet.