The universality problem over a unary alphabet: Decide if a unary NFA rejects a string. I believe that this is NP complete, but I am unsure of how to prove it. One possible idea I have is to split it into DFAs, then use the result here: NP-complete decision problems on deterministic automata, then complement all states, then determine if the intersection of the DFA accepts some common word. If it accepts a common word, then it would have rejected it in the original NFA.

I am aware that if it not unary, then it would be PSPACE complete, and is not NP complete unless PSPACE = NP



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.