<p>One interesting question about complexity classes over a unary alphabet that is not in the above references is the strength of Valiant's class #P<sub>1</sub>, the class of counting problems over a unary alphabet (see <a href="http://epubs.siam.org/doi/abs/10.1137/0208032">http://epubs.siam.org/doi/abs/10.1137/0208032</a>).  Not much is known about its power, though it has natural complete problems and, like unary languages, has polynomial-size circuits.</p>

CC BY-SA 3.0
2015-05-11T23:00:39.507Z
2015-05-11T23:00:39.507Z
Paul Beame
<p>There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the <a href="http://pighizzini.di.unimi.it/talks/2014/ciaa2014-full.pdf">slides</a> from his talk.</p>

<ul>
<li>Giovanni Pighizzini, <em>Investigations on Automata and Languages over a Unary Alphabet</em>, CIAA 2014.  doi:<a href="http://dx.doi.org/10.1007/978-3-319-08846-4_3">10.1007/978-3-319-08846-4_3</a></li>
</ul>

CC BY-SA 3.0
2015-05-11T15:00:06.233Z
2015-05-11T15:00:06.233Z
András Salamon
<p>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 ?</p>

CC BY-SA 3.0
2015-05-11T14:49:29.773Z
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
CC BY-SA 3.0
2015-07-06T17:25:39.557Z
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
<cc.complexity-theory><reference-request><big-list>
Complexity zoo for unary languages
J.-E. Pin
# Complexity zoo for unary languages

(Asked by: username_0 on 2015-05-11)

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 ?

**Tags:** cc.complexity-theory, reference-request, big-list
> **Comments:**
> **username_1**: 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  
> **username_2**: 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  

---

## 2 answers

### Answer by username_4 on 2015-05-11. Score: 23 | Accepted answer

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the [slides](http://pighizzini.di.unimi.it/talks/2014/ciaa2014-full.pdf) 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](http://dx.doi.org/10.1007/978-3-319-08846-4_3)


---

### Answer by username_3 on 2015-05-11. Score: 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.


---

