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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityConsider 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?
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).
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.