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$
$\endgroup$
3
-
$\begingroup$ Can't emptiness just be determined by searching the graph? That's O(n^2) at most, right? $\endgroup$– Harry AltmanCommented May 12, 2010 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 KontorovichCommented May 12, 2010 at 8:06
-
$\begingroup$ @Aryeh: I edited your question to reflect your comment. $\endgroup$– Neel KrishnaswamiCommented May 12, 2010 at 8:43
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
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).
answered May 12, 2010 at 18:37
-
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$– JBLCommented May 13, 2010 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$ Commented May 13, 2010 at 8:51
-
$\begingroup$ +1 Grigory, very nice! $\endgroup$ Commented May 13, 2010 at 10:51
-
$\begingroup$ Okay, with the additional word "minimal" I retract my complaint -- nice. $\endgroup$– JBLCommented May 13, 2010 at 13:06
-
$\begingroup$
$\endgroup$
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)?
answered May 13, 2010 at 3:17
$\begingroup$
$\endgroup$
3
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$– JBLCommented May 13, 2010 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$ Commented May 13, 2010 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$ Commented May 13, 2010 at 9:33