Als «space-bounded» getaggte Fragen

Dies könnte eher eine subjektive Frage als eine konkrete Antwort sein, aber trotzdem. In der Komplexitätstheorie untersuchen wir den Begriff effizienter Berechnungen. Es gibt Klassen wie für Polynomial Time und für Log Space . Beide werden als eine Art "Effizienz" angesehen und erfassen die...

Definieren Sie LOGLOG als die Klasse von Sprachen, die von einer deterministischen Turing-Maschine (mit bidirektionalem Zugriff auf die Eingabe) in Raum O (loglog n) berechnet werden können. Definieren Sie NLOGLOG auf ähnliche Weise als die Klasse von Sprachen, die von einer nicht deterministischen...

Die ST-Konnektivität ist das Problem, zu bestimmen, ob in einem gerichteten Graphen ein gerichteter Pfad zwischen zwei getrennten Eckpunkten und . Ob dieses Problem im Logspace gelöst werden kann, ist ein seit langem offenes Problem. Dies nennt man das vs Problem.ssstttG(V,E)G(V,E)G(V,E)NLNLNLLLL...

Zunächst entschuldige ich mich im Voraus für jede Dummheit. Ich bin kein Experte für Komplexitätstheorie (ganz im Gegenteil! Ich bin ein Student, der meinen ersten Kurs in Komplexitätstheorie belegt). Hier ist meine Frage. Nun besagt der Satz von Savitch, dass Nun bin ich gespannt, ob diese untere...

Es ist bekannt , dass gerichtet st-Konnektivität ist NLNLNL -komplette. Das bahnbrechende Ergebnis von Reingold zeigte, dass die ungerichtete st-Konnektivität in . Es ist bekannt, dass planar gerichtete st-Konnektivität in . Cho und Huynh definierten ein parametrisiertes Rucksackproblem und zeigten...

Es ist klar, dass jedes Problem, das im deterministischen Lograum ( ) entscheidbar ist, höchstens zur Polynomzeit ( P ) auftritt . Zwischen L und P gibt es eine Fülle von Komplexitätsklassen . Beispiele umfassen N L , L o g C F L , N C i , S A C i , A C i , S C i . Es wird allgemein angenommen ,...

Die Baumbreite misst, wie nah ein Diagramm an einem Baum ist. Es ist NP-schwer, die Baumbreite zu berechnen. Der bekannteste Näherungsalgorithmus erreicht Faktor.O(logn−−−−√)O(logn)O(\sqrt{{\log}n}) Courcelles Theorem besagt, dass jede Eigenschaft von Graphen, die in der monadischen Logik zweiter...

Ich frage mich, ob es eine Rechtfertigung dafür gibt, zu glauben, dass oder dass N L ≠ L ist .NL = LNL=LNL=LNL ≠ LNL≠LNL\neq L Es ist bekannt, dass . Die Literatur zur Derandomisierung von R L ist ziemlich überzeugend, dass R L = L ist . Kennt jemand einige Artikel oder Ideen, die davon überzeugen,...

Im Anschluss an eine vorherige Frage , was sind die besten aktuellen Raum untere Schranken für SAT? Mit einer Leerzeichenuntergrenze meine ich hier die Anzahl der von einer Turing-Maschine verwendeten Arbeitsbandzellen, die ein binäres Arbeitsbandalphabet verwendet. Ein konstanter additiver Term...

Betrachten Sie die Sprache .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Es ist bekannt, dass von keiner sublogarithmisch-raumwechselnden Turing-Maschine (ATM) erkannt werden kann (Szepietowski, 1994) . (Es gibt einen Geldautomaten, der sublogarithmischen...

Immerman und Szelepcsenyi bewiesen unabhängig voneinander, dass . Borodin et al. Haben mit ihrer Technik des induktiven Zählens bewiesen, dass S A C i unter Komplementation für i > 0 geschlossen ist . Vor dem Reingold Satz ( S L = L ), Nisan und Ta-Shma bewiesen S L = c o S L , logspace...

Im Allgemeinen zählt das Abfrageband für ein Orakel für die räumliche Komplexität eines TM. Es erscheint jedoch plausibel, nur ein beschreibbares Orakelband zuzulassen (wie es bei L-Platz-Verkleinerungen verwendet wird). Ist eine solche Konstruktion sinnvoll? Ergibt es irgendwelche besonders...

USTCONN ist das Problem, bei dem entschieden werden muss, ob es in einem Graphen einen Pfad vom Quellscheitelpunkt zum Zielscheitelpunkt gibt, der alle als Teil der Eingabe angegeben wird.ssstttGGG Omer Reingold hat gezeigt, dass USTCONN in L ist (doi: 10.1145 / 1391289.1391291 ). Der Proof...

In einer klassischen Arbeit untersuchen Munro und Paterson das Problem, wie viel Speicher erforderlich ist, damit ein Algorithmus den Median in einem zufällig sortierten Array findet. Insbesondere konzentrieren sie sich auf das folgende Modell: Die Eingabe wird P-mal von links nach rechts gelesen....

Kürzlich haben Watrous et al. Bewiesen, dass QIP (3) = PSPACE ein bemerkenswertes Ergebnis ist. Das war, gelinde gesagt, ein überraschendes Ergebnis für mich und hat mich zum Nachdenken angeregt ... Ich fragte mich, was wäre, wenn Quantencomputer durch klassische Computer effizient simuliert werden...

Es gibt eine Vielzahl von Algorithmen, die eine kontextfreie Grammatik in analysieren können.. Mit der Matrixmultiplikation kann man sogar asymptotisch schneller gehen.O(n3)O(n3)O(n^3) Alle Algorithmen zum Parsen beliebiger CFGs, die ich kenne, haben jedoch eine schlechteste Raumnutzung von (obwohl...

Eine Distribution soll -fool eine Funktion wenn . Und es wird gesagt, dass es eine Klasse von Funktionen täuscht, wenn es jede Funktion in dieser Klasse täuscht. Es ist bekannt, dass durch voreingenommene Räume die Klasse der Paritäten über Teilmengen täuschen. (siehe Alon-Goldreich-Hastad-Peralta...

Es ist leicht zu erkennen, dass jedes Problem, das im deterministischen Lograum ( ) entscheidbar ist, höchstens zur Polynomzeit ( P ) auftritt . Viele bekannte logspace Algorithmen (zum Beispiel: ungerichteten st-Konnektivität, planar Graphisomorphie) laufen in O ( n k ) , wobei k irrsinnig groß...

Die zeitbegrenzte Quantenberechnung ist offensichtlich sehr interessant. Was ist mit weltraumgebundener Quantenberechnung? Ich kenne viele interessante Ergebnisse für die Quantenberechnung mit sublogarithmischen Raumgrenzen und verschiedenen Arten von Quantenautomatenmodellen. Andererseits wurde...

Nisan hat in "Pseudozufallsgeneratoren für weltraumgebundene Berechnungen" bewiesen, dass es einen Pseudozufallsgenerator gibt, der weltraumgebundene Berechnungen "täuscht". Gilt diese Konstruktion für jedes Orakel (zumindest für nicht adaptive