25
$\begingroup$

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 ?

$\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$ May 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$ Jul 6, 2015 at 17:25

2 Answers 2

23
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.