26

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 ?

J.-E. Pin
  • 4,831
  • 26
  • 42
  • 7
    Of course, it is unknown whether there exists an NP-complete unary language. See this for more: http://en.wikipedia.org/wiki/Unary_language#Relationships_to_other_complexity_classes – Ryan Dougherty May 11 '15 at 14:49
  • Not exactly what you are looking for, but here is mini zoo with some languages reducible to unary languages. http://arxiv.org/abs/1212.3282 – Niall Murphy Jul 06 '15 at 17:25

2 Answers2

23

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
12

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.

Paul Beame
  • 121
  • 2