Por supuesto, algunos resultados de complejidad pueden colapsar para los idiomas unarios, pero me pregunto si hay alguna encuesta que resuma los resultados conocidos en este caso: una especie de zoológico de complejidad para los idiomas unarios. ¿Sabrías de tal referencia?
cc.complexity-theory
reference-request
big-list
J.-E. Alfiler
fuente
fuente
Respuestas:
Todavía no hay una referencia de estilo zoológico, pero una reciente encuesta teórica de autómatas de Giovanni Pighizzini me ha sido útil, especialmente las diapositivas de su charla.
fuente
Una pregunta interesante sobre las clases de complejidad sobre un alfabeto unario que no está en las referencias anteriores es la fuerza de la clase de Valiant #P 1 , la clase de problemas de conteo sobre un alfabeto unario (ver http://epubs.siam.org/doi/ abs / 10.1137 / 0208032 ). No se sabe mucho acerca de su poder, aunque tiene problemas naturales completos y, como los lenguajes unarios, tiene circuitos de tamaño polinómico.
fuente