Maschinencharakterisierung von

14

ist die Klasse von Entscheidungsproblemen, die durch eine Familie von O ( log i n ) -Tiefenschaltungen mit UND-Gattern mit unbegrenztem Fanin-ODER und begrenztem Fanin lösbar sind. Negationen sind nur auf der Eingangsebene zulässig. Es ist bekannt, dassfürunter Komplement abgeschlossen ist undnicht. Außerdem istund weist daher eine Maschinencharakterisierung auf, daLogCFL?SACiO(login)SACii1SAC0SAC1=LogCFL die Menge von Sprachen ist, die von einem Polynom- Hilfs-PDA akzeptiert werden . Gibt es ähnliche Maschinencharakterisierungen von fürO(logn)SACii2

Shiva Kintali
quelle
Sollen und ich dasselbe sein? ki
András Salamon
Ja. Entschuldigung für den Tippfehler. Behebt es jetzt.
Shiva Kintali

Antworten:

14

Ja. Stapelhöhen. , das, mit ist O ( log n ) Raum und O ( log n ) Stapelhöhe; Dies impliziert log n Konfigurationen und log 2 ( n ) Bits. Wir habenSAC1=NAuxPDA(logn,logn)O(logn)O(logn)lognlog2(n)

SACk=NAuxPDA(logn,logkn);

Diese Maschinen werden in Zeit . Ohne Beschränkung auf Stapelhöhe, erhalten wir genau P . Das Ergebnis sollte sich ergeben aus: W. Ruzzo, baumgrößenbegrenzter Wechsel. JCSS 1980.2logk(n)P

V Vinay
quelle
Vinay, Sie können reguläres Latex in der Antwort verwenden: Es könnte helfen, es ein bisschen lesbarer zu machen
Suresh Venkat