Maschinencharakterisierung von

ist die Klasse von Entscheidungsproblemen, die durch eine Familie von -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? $SAC^i$ $O({\log}^i{n})$ $SAC^i$ $i \geq 1$ $SAC^0$ $SAC^1 = LogCFL$ die Menge von Sprachen ist, die von einem Polynom- Hilfs-PDA akzeptiert werden . Gibt es ähnliche Maschinencharakterisierungen von für $O({\log}n)$ $SAC^i$ $i \geq 2$

cc.complexity-theory circuit-complexity space-bounded arithmetic-circuits Shiva Kintali
quelle

Sollen

und

dasselbe sein?

k

$k$

i

$i$

András Salamon

Ja. Entschuldigung für den Tippfehler. Behebt es jetzt.

Shiva Kintali

Antworten:

Ja. Stapelhöhen. , das, mit ist Raum und Stapelhöhe; Dies impliziert Konfigurationen und Bits. Wir haben $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$ $O(\log n)$ $O(\log n)$ $\log n$ $\log^2(n)$

S A C^{k} = N A u x P D A (\log n, \log^{k} n);

$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$

Diese Maschinen werden in Zeit . Ohne Beschränkung auf Stapelhöhe, erhalten wir genau . Das Ergebnis sollte sich ergeben aus: W. Ruzzo, baumgrößenbegrenzter Wechsel. JCSS 1980. $2^{\log^{k}(n)}$ $\mathsf{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