Does a given e-NFA accepts all the Strings?

Question

Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by it.

Of course the usual way is to construct a DFA, or complement the e-NFA but since we are talking about the whole language, I was wondering if there is a much more efficent method in the worst case.

Answer 1

A classical result, attributed to Meyer and Stockmeyer, is that checking whether an NFA accepts all strings is PSPACE-complete. Nevertheless, there are some non-trivial heuristic algorithms. See for example Antichains: A New Algorithm for Checking Universality of Finite Automata by De Wulf, Doyen, Henzinger and Raskin.