Komplexitätszoo für unäre Sprachen

25

Natürlich können einige Komplexitätsergebnisse für unäre Sprachen zusammenbrechen, aber ich frage mich, ob es in diesem Fall eine Umfrage gibt, die die bekannten Ergebnisse zusammenfasst: eine Art Komplexitätszoo für unäre Sprachen. Wussten Sie von einer solchen Referenz?

cc.complexity-theory reference-request big-list J.-E. Stift
quelle
7
Natürlich ist nicht bekannt, ob es eine NP-vollständige unäre Sprache gibt. Weitere
Ryan
Nicht genau das, wonach Sie suchen, aber hier ist ein Mini-Zoo mit einigen Sprachen, die auf unäre Sprachen reduziert werden können. arxiv.org/abs/1212.3282
Niall Murphy

Antworten:

23

Es gibt noch keine Referenz im Zoo-Stil, aber eine aktuelle automaten-theoretische Übersicht über Giovanni Pighizzini hat mir geholfen, insbesondere die Folien aus seinem Vortrag.

András Salamon
quelle
12

Eine interessante Frage zu Komplexitätsklassen über ein unäres Alphabet, die nicht in den obigen Referenzen aufgeführt ist, ist die Stärke der Klasse #P 1 von Valiant , der Klasse für Zählprobleme über ein unäres Alphabet (siehe http://epubs.siam.org/doi/). abs / 10.1137 / 0208032 ). Es ist nicht viel über seine Leistungsfähigkeit bekannt, obwohl es natürliche vollständige Probleme hat und wie unäre Sprachen Schaltkreise in Polynomgröße hat.

Paul Beame
quelle