The Fooling Set Problem for Unary Regular Language Is in NP
Dongcai Shen, Tian Liu · 2008
In recent years, the fooling set technique has been used to find the lower bounds for nondeterministic state complexity of regular languages. For regular languages in general, the decision version of this problem has not been classified into a certain exact complexity group, but has been proved to be NP-hard and be contained in PSPACE. In this article, fooling set problem of unary regular language is discussed, and proved to be in NP.