Emptiness and determinization of NFAs - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:34:10Z http://mathoverflow.net/feeds/question/24343 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas Emptiness and determinization of NFAs Aryeh Kontorovich 2010-05-12T07:30:01Z 2010-05-13T15:12:33Z <p>Consider an NFA on n states. Is it possible to determine whether it accepts all strings in poly(n) time?</p> <p>Suppose the NFA above has an equivalent DFA on d states. Is it possible to construct this DFA in poly(n,d) time?</p> http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422 Answer by Grigory Yaroslavtsev for Emptiness and determinization of NFAs Grigory Yaroslavtsev 2010-05-12T18:37:49Z 2010-05-13T15:12:33Z <p>What you are asking about is known as the universality problem. In the slides by Jeffrey Shallit (http://www.cs.uwaterloo.ca/~shallit/Talks/open10r.pdf, slide 36) it is mentioned that this problem is PSPACE-complete for NFA. So it is highly unlikely that a polynomial algorithm exists for it. <strike>Please, let me know if you need an exact reference to the proof of the PSPACE-completeness</strike> (see edit2).</p> <p>edit. I forgot to mention that because the universality problem for DFA is simply solved in polynomial time the existence of a poly(n, d) algorithm in your second question also implies PSPACE=P and is very unlikely.</p> <p>edit2. The proof of PSPACE-completeness can be found in the lecture notes here: <a href="http://www.wisdom.weizmann.ac.il/~vardi/av/notes/" rel="nofollow">http://www.wisdom.weizmann.ac.il/~vardi/av/notes/</a> (the proof itself is in lecture 4).</p> http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24423#24423 Answer by Niall Murphy for Emptiness and determinization of NFAs Niall Murphy 2010-05-12T18:47:40Z 2010-05-13T09:56:42Z <p>To determine if an NFA $M$ accepts all strings you can first construct the machine that accepts the complement language $\overline{M}$ (here is the exponential bottleneck since you must first convert to a DFA). Then you can use Harry Altman's suggestion to check for emptiness.</p> <p>To convert $M$ with $n$ states which accepts a language $L$ to a DFA $D$ which also accepts $L$ but using $d$ steps in poly$(n,d)$ time on a Turing machine is easy, however $d$ in the worst case is exponential in $n$ (using the naive algorithm undergrads learn). This problem is very well studied and in practice many programmes use tricks to do this more efficiently. I'm not at all familiar with these though so I cannot say if they use poly$(n)$ space and time average case.</p> http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24469#24469 Answer by Joel David Hamkins for Emptiness and determinization of NFAs Joel David Hamkins 2010-05-13T03:17:13Z 2010-05-13T03:17:13Z <p>Your second question is a little ambiguous, because it admits the following cheating affirmative answer, which is probably not what you intend. </p> <p>Namely, every NFA with n states is equivalent to a DFA with d states for d sufficiently large. And for large $d$, allowing poly(n,d) steps is plenty of time. The well-known equivalent DFA, such as the one provided in Sipser's book, has $2^n$ states (plus a constant), and this example can be constructed in poly(n,2^n) steps, simply because $d=2^n$ is already so large here. More generally, for even larger $d$, we can simply pad this one with extra irrelevant states, and build it also in poly(n,d) steps. </p> <p>Perhaps you mean to ask about the optimal $d$? Or do you want to ask for all $d$ for which there is an equivalent DFA with $d$ states? Or do you also want to ask whether the optimal $d$ itself is poly(n)? </p> http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24476#24476 Answer by Aryeh Kontorovich for Emptiness and determinization of NFAs Aryeh Kontorovich 2010-05-13T06:10:23Z 2010-05-13T06:10:23Z <p>Thanks to everyone for the answers. I agree with both of Joel's comments:</p> <ol> <li>I don't think Niall's construction is necessarily polynomial in n.</li> <li>I meant that the DFA equivalent to the given NFA is minimal (thus, the d is optimal).</li> </ol> <p>Grigory, would it be possible to obtain a reference for the PSPACE-completeness proof?</p> <p>Many thanks!</p>