24
$\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$
  • 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 May 11 '15 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 Murphy Jul 6 '15 at 17:25
22
$\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$
11
$\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, privacy policy and cookie policy

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