Effiziente Logspace-Algorithmen

17

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ß ist.LPO(nk)k

  • Ich suche nach Beispielen für natürliche Probleme, von denen bekannt ist, dass sie gleichzeitig im deterministischen logarithmischen Raum und in der -Zeit lösbar sind, wobei k 10 ist . Es gibt nichts Besonderes an 10. Wenn man sich die derzeit bekannten Logspace-Algorithmen ansieht, denke ich, dass k 10 interessant genug ist.O(nk)k10k10
  • Aleliunas et al. zeigten, dass ungerichtete st-Konnektivität in (randomisierten logspace) ist. Die Laufzeit ihres Algorithmus ist O ( n 3 ) . Gibt es natürliche Probleme, die gleichzeitig in R L und linearer Zeit (oder nahezu linearer Zeit) gelöst werden können, dh -Zeit?RLO(n3)RLO(nlogin)

Edit: Um die Sache interessanter zu machen, schauen wir uns Probleme an, die mindestens -hart sind.NC1

Shiva Kintali
quelle
Gibt es eine Zeitanalyse für die Logspace-Version von Courcelles Theorem? eccc.uni-trier.de/report/2010/062
Hsien-Chih Chang 張顯 之

Antworten:

10

Ich denke, Single-Source Single-Sink Planar DAG (SSPD) Erreichbarkeit hat Logspace-Algorithmus mit einer bescheidenen Laufzeit ( O(n2) ?). Ich bin mir hinsichtlich des Single-Source-Multiple-Sink-SMPD-Algorithmus (Planar DAG Reachability) nicht so sicher.

Referenz: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta und Sambuddha Roy: Probleme mit der Erreichbarkeit von Ebenen- und Gittergraphen Theory Comput. Syst. 45 (4): 675-723 (2009)

Außerdem läuft ein neuer Logspace-Algorithmus zum Testen und Einbetten der Planarität in mäßig polynomialer Zeit (Modulo natürlich ungerichtete Erreichbarkeit).

Ref: Samir Datta, Gautam Prakriya: Planaritätstest überarbeitet AdRR abs / 1101.2637: (2011)

Schließlich ist hier ein einfaches Spielzeugproblem, das einen logspace algo mit einer bescheidenen Laufzeit (modulo ungerichtete Erreichbarkeit) nämlich hat. Äußerer planarer Isomorphismus.

SamiD
quelle
1
Der SSPD-Algorithmus ist nachdem die planare Einbettung gefunden wurde, und verwendet die Tatsache, dass linearer zeitlicher, logarithmischer Laufweg "ganz links" und "ganz rechts" von jedem Scheitelpunkt zur Senke oder vorhanden ist die Quelle zu einem beliebigen Scheitelpunkt (nennen Sie diese "äußeren" Pfade). Um einen Pfad von u nach v zu finden , überprüfen Sie, ob die Scheitelpunkte auf den äußeren Pfaden von u nach Senke auf den äußeren Pfaden von der Quelle nach v liegen.O(n2)uv
Derrick Stolee
9

Diese Antwort ist eher ein Spielzeugproblem als ein echtes Forschungsproblem.

Mein typisches Beispiel für einen Log-Space-Algorithmus, den ich Programmierfreunden geben möchte, ist das folgende Rätsel:

n

O(logn)

  • Stellen Sie den ersten Zeiger in der Liste um einen Schritt vor.
  • Stellen Sie den zweiten Zeiger in der Liste in zwei Schritten vor.
  • Wenn einer der Zeiger das Ende findet, geben Sie false zurück.
  • Wenn die Knoten auf denselben Knoten zeigen, geben Sie true zurück.
  • Andernfalls wiederholen Sie den Vorgang erneut.

nn

Derrick Stolee
quelle
3
NC1
3

O(n) -Graph-Markierungsalgorithmus, dessen Varianten das Herz vieler Garbage-Collector-Implementierungen bilden. Das Problem besteht darin, die Knoten eines Graphen zu markieren, die von einem Wurzelknoten aus erreichbar sind. Die naive rekursive Durchquerung benötigt linearen Raum, um den Stapel der besuchten Knoten zu halten, aber der DSW-Algorithmus codiert diesen Stapel durch einen listigen Linkumkehrtrick - wenn er einer Kante folgt, ändert er die Kante, der er gefolgt ist, um die Quelle und das Ziel umzukehren dass es den Stapel im Diagramm selbst codieren kann.

NC1

Neel Krishnaswami
quelle
2
Da Sie das Diagramm ändern, handelt es sich nicht um einen Protokollbereichsalgorithmus, bei dem das Eingabeband schreibgeschützt sein muss. Dies ist ein interessanter Algorithmus für sich.
Derrick Stolee