Of course, some complexity results may collapse for unary languages but I wonder if there is somewhere a survey summarizing the known results in this case: a kind of complexity zoo for unary languages. Would you know of such a reference ?
$\begingroup$
$\endgroup$
2
-
7$\begingroup$ Of course, it is unknown whether there exists an NP-complete unary language. See this for more: en.wikipedia.org/wiki/… $\endgroup$– Ryan DoughertyMay 11, 2015 at 14:49
-
$\begingroup$ Not exactly what you are looking for, but here is mini zoo with some languages reducible to unary languages. arxiv.org/abs/1212.3282 $\endgroup$– Niall MurphyJul 6, 2015 at 17:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk.
- Giovanni Pighizzini, Investigations on Automata and Languages over a Unary Alphabet, CIAA 2014. doi:10.1007/978-3-319-08846-4_3
answered May 11, 2015 at 15:00
$\begingroup$
$\endgroup$
One interesting question about complexity classes over a unary alphabet that is not in the above references is the strength of Valiant's class #P1, the class of counting problems over a unary alphabet (see http://epubs.siam.org/doi/abs/10.1137/0208032). Not much is known about its power, though it has natural complete problems and, like unary languages, has polynomial-size circuits.
