Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.