Beziehung zwischen Algorithmuskomplexität und Automatenklasse

Ich konnte kein Diagramm finden, das die folgende Frage darstellt oder Text beantwortet: Gibt es einen direkten Zusammenhang zwischen der Komplexität eines Algorithmus (z. B. Best / Worst-Fall der schnellen Sortierung) und der Klasse von Automaten, die den Algorithmus implementieren können? Gibt es zum Beispiel eine Reihe von Komplexität, die Push-Down-Automaten ausdrücken können? Wenn die Antwort auf diese Frage Ja lautet, gibt es eine Ressource, die die Beziehung darstellt? Vielen Dank!

Ja, in vielen Fällen gibt es Beziehungen!

Beispielsweise ist bekannt, dass jede Sprache, die von umkehrbegrenzten Zählermaschinen akzeptiert wird, in (siehe hier ).$P$

In ähnlicher Weise wissen wir, dass alle regulären Sprachen in , da es einen Polynomzeitalgorithmus gibt, um zu bestimmen, ob eine NFA ein bestimmtes Wort akzeptiert.$P$

Es gibt zu viele, um sie hier aufzuzählen, aber im Allgemeinen befinden sich eingeschränktere Berechnungsmodelle in einfacheren Komplexitätsklassen.

Hier sind einige bekannte Ergebnisse:

1. , wobei R E $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$$\mathsf{REG}$ist die Menge der regulären Sprachen. Für Beweise finden Sie auf der Wikipedia - Seite über $\mathsf{DSPACE}$ .

2. , wobei D C F L die Menge der deterministisch kontextfreien Sprachen ist, und S C istSteves Klasse. Sehendie WikipediaSeite über D C F L .$\mathsf{DCFL} \subseteq \mathsf{SC}$$\mathsf{DCFL}$$\mathsf{SC}$$\mathsf{DCFL}$

3. , wobei L O G C F L die Menge der Sprachen ist, die logarithmisch auf eine kontextfreie Sprache reduziert werden können. WeitereInformationen findenSie auf der Wikipedia-Seite zu L O G C F L , auf der auch einige Sprachen für L O G C F L unter Logspace-Reduzierung aufgeführt sind.$\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$$\mathsf{LOGCFL}$$\mathsf{LOGCFL}$$\mathsf{LOGCFL}$

4. , wobei C S L die Menge der kontextsensitiven Sprachen ist. Sehendie WikipediaSeite über C S L .$\mathsf{CSL} = \mathsf{NSPACE}(n)$$\mathsf{CSL}$$\mathsf{CSL}$

5. Die Klasse von Sprachen, die von deterministischen nicht löschenden PDAs akzeptiert werden, ist , und die Klasse von Sprachen, die von nicht deterministischen nicht löschenden PDAs akzeptiert wird, ist N S P A C E ( n 2 ) . Siehe die Wikipedia-Seite zu PDAs .$\mathsf{DSPACE(n\log n)}$$\mathsf{NSPACE}(n^2)$

6. Zwei-Stapel-Automaten haben die gleiche Leistung wie Turing-Maschinen, aber die Einschränkung der Automaten führt zu schwächeren Modellen. Siehe einen technischen Bericht von San Pietro.

Gibt es eine direkte Beziehung zwischen der Komplexität eines Algorithmus (z. B. Best / Worst-Fall der schnellen Sortierung) und der Klasse von Automaten, die den Algorithmus implementieren können?

Die Frage, welche Klasse von Automaten einen bestimmten Algorithmus wie die schnelle Sortierung implementieren kann, ist schwierig, da unklar ist, was als Implementierung dieses Algorithmus gelten würde. Für eine schnelle Sortierung sollten die durchgeführten Vergleiche sicherlich gleich sein, aber muss die Reihenfolge, in der die Vergleiche durchgeführt werden, auch dieselbe sein? Was ist mit der Reihenfolge der Lesezugriffe auf bestimmte Elemente der Eingabe? Die Reihenfolge der Kopier-, Verschiebungs- und Austauschvorgänge für bestimmte Elemente?

Sie müssten eine ganze Reihe von Orakeln für die Operationen angeben, die für Sie wichtig sind, aber dann befinden Sie sich bereits in einer sehr spezifischen Situation, die auf dem Algorithmus basiert, und sind weit entfernt von den allgemeinen Klassen von Automaten, die üblicherweise studiert werden. Der Weg um dieses Dilemma besteht darin, über Probleme anstelle von Algorithmen zu sprechen und Probleme zu formalisieren, indem über Sprachen gesprochen wird.

Gibt es zum Beispiel eine Reihe von Komplexität, die Push-Down-Automaten ausdrücken können?

Nicht wirklich, denn Push-Down-Automaten können ihre Eingabe nur einmal und nur in Vorwärtsrichtung lesen. Wenn Sie die Maschine jedoch in einen Teil aufteilen, der die Eingabe nach Belieben vorwärts und rückwärts lesen darf, und eine endliche Anzahl von Zeigern auf bestimmte Eingabepositionen (NL) beibehalten, und einen Teil, der Push-Down-Automaten empfängt Wenn Sie ihn vom anderen Teil eingeben , erhalten Sie die Komplexitätsklasse LOGCFL , die gleich SAC ¹ (eine Schaltungsklasse) ist.

Wenn Sie diese beiden Teile nicht trennen und nur einen Stapel zu NL hinzufügen, erhalten Sie die Automatenklasse AuxPDA , die der Komplexitätsklasse P entspricht . Wenn Sie jedoch die Laufzeit dieser Automaten (mit Stapel und logarithmischem Hilfsspeicher ) auf die Polynomzeit beschränken, erhalten Sie NAuxPDA ^P , das wiederum LOGCFL entspricht. (Und wenn Sie auf einer deterministischen Polynomlaufzeit bestehen, den Stapel verschrotten, aber eine polylogarithmische Hilfsspeicherung zulassen, erhalten Sie SC .)

Wenn Sie jedoch die Einschränkung beibehalten, dass die Automaten ihre Eingabe nur einmal und nur in Vorwärtsrichtung lesen können, und zusätzlich verlangen, dass sie ihren Stapel nur auf sehr deterministische Weise direkt basierend auf der Eingabe (dh dem Eingabesymbol) verwenden können Bestimmt, ob diese Automaten etwas auf den Stapel schieben, etwas aus dem Stapel entfernen oder den Stapel unberührt lassen, erhalten Sie sichtbar Pushdown-Automaten, die genau die verschachtelten Wortsprachen erkennen , die auch im deterministischen logarithmischen Raum erkannt werden können .