7
$\begingroup$

It is well known that the universality problem for NFA (deciding whether $L(A)=\Sigma^*$) is $PSPACE$-complete. However, what if every state of the NFA is known to be accepting? It seems to me that the problem is at most in $co$-$NP$, as a counterexample (unlike in the case of a general NFA) is polynomial (even linear) in the size of the input (the number of states). What is the complexity of this problem?

$\endgroup$
  • 1
    $\begingroup$ Unless there's a problem in my proof, it's very unlikely that your problem is co-NP because it'd imply that co-NP = PSPACE. Since a counterexample (i.e. a rejected word) could indeed be checked in time polynomial in its size, I'd be temped to say that there must be a problem in your proof that there is always a counterexample of polynomial size. Could you please explain how you would find such a polynomial size counterexample? The only thing I could think of was searching for a shortest path to a state in which the transition function isn't total but there could be another path that works... $\endgroup$ – xavierm02 Feb 10 '17 at 14:29
  • 2
    $\begingroup$ It's not true that the shortest counterexample has polynomial size. Consider an NFA whose initial state is connected to cycles of lengths $2,p_1,\ldots,p_m$. You can arrange for the word $1^n0$ not to be accepted only if $n$ is odd and a multiple of $p_1,\ldots,p_m$. By choosing the $p_i$ to be the first $m+1$ primes, you obtain an NFA with $O(m^2\log m)$ states in which the shortest rejected word has length $e^{(1+o(1))m\log m}$. $\endgroup$ – Yuval Filmus Feb 10 '17 at 14:43
  • 1
    $\begingroup$ A simple reduction from SAT shows that the problem is indeed coNP-hard. The NFA branches into parts according to the clauses. Each part checks whether the input, which consists of an assignment followed by $\$$, satisfies the clause, and if so gets stuck at the final $\$$. This NFA is not universal iff the SAT instance is satisfiable. $\endgroup$ – Yuval Filmus Feb 10 '17 at 14:49
  • $\begingroup$ @YuvalFilmus You are correct regarding the counterexample, but as it turns out I misstated the problem. I know that $L(A)$ has no words with consecutive repeating letters, and I'm looking for universality with respect to all words with no consecutive repeating letters. Is there an exponential counterexample in that case, too? $\endgroup$ – pron Feb 10 '17 at 15:50
  • $\begingroup$ @YuvalFilmus In addition, the alphabet is no bigger than the number of states + 1. $\endgroup$ – pron Feb 10 '17 at 15:59
4
$\begingroup$

You problem is PSPACE-complete. I prove that it's PSPACE-hard by reducing universality of NFAs to universality of NFAs with all states accepting.


Let $A$ be a NFA. Add a new final state $q_\$$ to it and for every accepting state $q$, add a transition $q\overset{\$}{\to}q_\$$ where $\$$ is a fresh letter. For every letter $a\in \Sigma\sqcup \{\$\}$, also add a transition $q_\$\overset{a}{\to}q_\$$. And then make all states accepting. The new automaton accepts $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ for some $L'\subseteq \Sigma^*$.

Now, add some automaton (with all states final) that recognizes the language $\Sigma ^*$ (i.e. the language of words that don't contain $\$$) in parallel. The new automaton will recognize $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$.

Now, notice that we have $L(A)=\Sigma^*$ iff $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$. I.e. the process I described is a reduction from universality of a NFA to universality of a NFA with all states accepting. Since the reduction is polynomial, your problem is PSPACE-hard.

$\endgroup$
  • $\begingroup$ How do you construct an NFA for $\Sigma^* \setminus \Sigma^*\$$ all of whose states are accepting? $\endgroup$ – Yuval Filmus Feb 10 '17 at 14:32
  • $\begingroup$ Thank you, that's a nice reduction, and indeed answers my question. However, I had a different, more complex question in mind which I had thought I could reduce to this one, and @YuvalFilmus 's exponential counterexample made me realize that my own reduction was faulty, and I should have added the constraint that $L(A)$ does not contain words with repeated letters, and I'm checking for "universality" with respect to such words. $\endgroup$ – pron Feb 10 '17 at 15:43
  • $\begingroup$ @pron What do you mean by "word with repeated letters"? That $u=v_1aav_2$ or that $u=v_1av_2av_3$? $\endgroup$ – xavierm02 Feb 10 '17 at 15:49
  • $\begingroup$ @xavierm02 The first one, i.e., no consecutive repeated letters. Is there an exponential counterexample in that case, too? $\endgroup$ – pron Feb 10 '17 at 15:50
  • $\begingroup$ @xavierm02 Also, the alphabet is no bigger than the number of states + 1. $\endgroup$ – pron Feb 10 '17 at 15:58

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.