Alternative Beweise des Immerman-Szelepcsenyi-Theorems

20

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 einheitliche Projektion Reduzierungen verwenden. In einem 1996 von Alvarez und Greenlaw veröffentlichten Papier heißt es: "Ein Beweis von NNL=coNLSACii>0SL=LSL=coSL mit ähnlichen Techniken wie Nisan und Ta-Shma wurde nicht erreicht, obwohl ein solcher Beweis sehr interessant wäre. "Ich frage mich, ob ein solcher Beweis in den letzten 14 Jahren gefunden wurde. Gibt es andere alternative Beweise? von N L = c o N L ?NL=coNLNL=coNL

Shiva Kintali
quelle
1
Ein sehr ähnlicher Beweisstil wird von Reinhardt und Allender gegeben, um zu beweisen, dass St-Erreichbarkeitsgraphen mit einem eindeutigen Min-Längen-Pfad zwischen s und t in UL \ cap coUL bestimmt werden können.
Derrick Stolee
@Derrick: könntest du eine Antwort ausarbeiten?
András Salamon
@ András: Die Arbeit von Reinhardt und Allender verwendet das Lemma des induktiven Zählens und Isolierens, um zu zeigen, dass NL / poly = UL / poly, dh im Kontext einer ungleichmäßigen Komplexität, eine nicht deterministische lograumbegrenzte Berechnung eindeutig gemacht werden kann. Dies ist ein schönes verwandtes Ergebnis, verdient es jedoch nicht, als Antwort hinzugefügt zu werden.
Shiva Kintali

Antworten:

10

Kann ich einen Kommentar abgeben, da wir keine Antworten zu haben scheinen?

Angenommen, wir haben Bits, X = x 1n und wir müssen jedes Bit komplementieren, um ¬ x 1 , , ¬ x n zu erhalten . Die einzige Einschränkung ist, dass die Schaltung, die dies tut, monoton sein sollte. Wir brauchen offensichtlich einige zusätzliche Informationen, und hier ist eine solche.X=x1,,xn¬x1,,¬xn.

Angenommen, ist die Anzahl von Einsen in der Eingabe und irgendwie haben wir dies als Rat. Dann ist leicht zu erkennen, dass ¬ x i = T h n istk(heißt, an allen Eingängen außerxi). Die Konstruktion ist natürlich monoton.¬xi=Thkn1(Xxi)xi

Mit dieser Konstruktion ist die Motivation für das induktive Zählen klar (zumindest für mich). Es lohnt sich zu fragen, welche anderen Ratschläge funktionieren würden. Ich kenne keine andere. Dies könnte jedoch den Schlüssel zu Ihrer Frage enthalten.

V Vinay
quelle
4
O(logn)fff
@ Vinay, @ Ramprasad: Danke für die schönen Einblicke.
Shiva Kintali