Consider an NFA on n states. Is it possible to determine whether it accepts all strings in poly(n) time?

Suppose the NFA above has an equivalent DFA on d states. Is it possible to construct this DFA in poly(n,d) time?

  • $\begingroup$ Can't emptiness just be determined by searching the graph? That's O(n^2) at most, right? $\endgroup$ – Harry Altman May 12 '10 at 7:48
  • $\begingroup$ Oops, my mistake!!! I didn't mean emptiness -- I meant L(NFA) = \Sigma^*. That is, rather than checking whether NFA accepts no strings (trivial) I want to know if it accepts ALL strings. $\endgroup$ – Aryeh Kontorovich May 12 '10 at 8:06
  • $\begingroup$ @Aryeh: I edited your question to reflect your comment. $\endgroup$ – Neel Krishnaswami May 12 '10 at 8:43

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. Please, let me know if you need an exact reference to the proof of the PSPACE-completeness (see edit2).

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.

edit2. The proof of PSPACE-completeness can be found in the lecture notes here: http://www.wisdom.weizmann.ac.il/~vardi/av/notes/ (the proof itself is in lecture 4).

  • 1
    $\begingroup$ Grigory, your edit is definitely wrong unless you can guarantee that d is poly(n) -- if d is 2^n, then it takes exponential time to write down the DFA. $\endgroup$ – JBL May 13 '10 at 0:17
  • 1
    $\begingroup$ Suppose someone has developed a $poly(n,d)$-time algorithm $A(x)$ for the problem and we know this $poly(n,d)$, which is equal to some $p(n,d)$. Because for the minimal DFA that accepts all strings $d=1$, then the running time of the algorithm A is equal to some polynomial $q(n)$ if the given NFA is universal. If the given NFA is not universal than we just let A make $q(n)$ steps and terminate it if it hasn't terminated: either we found the DFA and can check directly or terminated and we know that the resulting DFA cannot be universal. $\endgroup$ – Grigory Yaroslavtsev May 13 '10 at 8:51
  • $\begingroup$ +1 Grigory, very nice! $\endgroup$ – Joel David Hamkins May 13 '10 at 10:51
  • $\begingroup$ Okay, with the additional word "minimal" I retract my complaint -- nice. $\endgroup$ – JBL May 13 '10 at 13:06
  • $\begingroup$ link in edit2 is broken. $\endgroup$ – 6005 Apr 26 '17 at 8:16

Your second question is a little ambiguous, because it admits the following cheating affirmative answer, which is probably not what you intend.

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.

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)?


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.

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.

  • $\begingroup$ Niall, what do you mean by the complement (sorry to be a pedant, but note the spelling) of an NFA? An NFA that accepts the complementary language? $\endgroup$ – JBL May 13 '10 at 0:18
  • 1
    $\begingroup$ To compute the complement, don't you first have to build the equivalent DFA? This could take more than poly(n) time. $\endgroup$ – Joel David Hamkins May 13 '10 at 3:18
  • $\begingroup$ Yes sorry I meant the complement (corrected). And yes, you will need exponential sequential time and as Grigory points out, the problem PSPACE complete. So polynomial parallel time if you have an exponential number of processors. $\endgroup$ – Niall Murphy May 13 '10 at 9:33

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.