Erfasst die Diagonalisierung das Wesen der Klassentrennung?

11

Ich kann mich nicht erinnern, eine Klassentrennung gesehen zu haben, die nicht auf Diagonalisierungs- und Relativierungsergebnissen basiert. Die Diagonalisierung könnte weiterhin verwendet werden, um verbleibende bekannte Klassen zu trennen, da nicht relativierende Argumente weiterhin in der Schlussfolgerung der Diagonalisierung oder in der diagonalisierten Turing-Maschinenkonstruktion verwendet werden könnten. Hier sind einige verwandte Fragen:

Gibt es Klassentrennungsbeweise, die nicht auf Diagonalisierung basieren?

Und wenn

Können wir einen Selbstreferenzmechanismus dahinter finden?

Des Weiteren,

Hat jede Klassentrennung einen "kanonischen natürlichen" Beweis (im informellen Sinne)?

Wenn ja, sollten wir versuchen, nicht relativierende Argumente zu finden, anstatt andere Beweisschemata für offene Fragen.

Kann jeder nicht diagonale Beweis in einen diagonalen umgeschrieben werden?

Ludovic Patey
quelle
Ich habe die Frage bearbeitet, um das Lesen zu erleichtern. Entschuldigung, wenn ich Ihre Absicht geändert habe.
András Salamon
@ András Vielen Dank für Ihre Ausgabe. Ich bin oft unklar. Es gibt eine Änderung: Ich meinte, dass die Diagonalisierung nicht fehlgeschlagen ist, weil wir darin nicht relativierende Argumente verwenden können. Ich denke, Relativierung und Diagonalisierung sind orthogonal. Und ich denke nicht, dass Beweise, die keine Diagonalisierung verwenden, einen tiefen Selbstreferenzmechanismus verwenden würden, sondern nur, dass wir bei einem tiefen Verständnis des Beweises einen tiefen Tiefenreferenzmechanismus entdecken könnten ^^. Ich werde diese besonderen Punkte erneut bearbeiten.
Ludovic Patey

Antworten:

15

Hängt davon ab, wie Sie die Diagonalisierung formalisieren. Kozen hat ein Papier , das zeigt, dass jede Trennung von Komplexitätsklassen ein Beweis für die Diagonalisierung sein muss.

Lance Fortnow
quelle
+1 Ich glaube, ich habe dies in Ihrem Blog gelesen und auf Ihre Antwort gewartet :)
Mohammad Al-Turkistany
5

Da die Diagonalisierung relativiert, kann ein Komplexitätsergebnis, das widersprüchliche Relativierungen impliziert, nicht auf der Diagonalisierung basieren. Zitiert Arora-Barak :

OO{0,1}

PNPPNP

PPHIP

MS Dousti
quelle
2
Beachten Sie, dass Baker, Gill und Solovay nicht sagten, dass Diagonalisierung nicht funktionieren kann, sondern eine differenziertere Aussage machten: "Es ist unwahrscheinlich, dass gewöhnliche Diagonalisierungsmethoden angemessen sind."
András Salamon
@Sadeq Ich stimme nicht zu, dass sich die Diagonalisierung relativiert. Beispielsweise könnten Sie eine diagonale Maschine basierend auf einer Eigenschaft definieren, die die Eigenschaft der Berechnungslokalität berücksichtigt, die nicht relativiert wird.
Ludovic Patey
Algebrisierung ist keine Technik, sondern ein der Relativisierung ähnliches Konzept. Ich nehme an, Sie meinen stattdessen Arithmetisierung. Und was ist die Verbindung zu natürlichen Beweisen?
Kristoffer Arnsfelt Hansen
1
@Sadeq: BGS erlaubte eindeutig eine umfassendere Definition der Diagonalisierung, als Arora-Barak zu beabsichtigen scheint. Wenn ein Mengen-Theoretiker wie Robert Solovay glaubt, dass es andere Begriffe der Diagonalisierung gibt, die sich nicht relativieren lassen, sollten wir diese Möglichkeit vielleicht offen lassen. Hinweis Seite 75 von A & B schließt die Möglichkeit nicht aus, dass bei einer Diagonalisierung eine nicht relativierende Tatsache über Turing-Maschinen verwendet wird. Das noch unveröffentlichte Manuskript von Arora-Impagliazzo-Vazirani weist darauf hin, dass es sich um recht subtile Themen handelt. cseweb.ucsd.edu/~russell/ias.ps
András Salamon
1
Es gibt einige Debatten darüber: siehe zum Beispiel Fortnows Antwort auf das AIV-Papier: people.cs.uchicago.edu/~fortnow/papers/relative.pdf
Suresh Venkat
5

Um Fortnows Antwort zu ergänzen, haben Nash, Impagliazzo und Remmel , die Kozens Arbeit fortsetzten, einen Begriff der starken Diagonalisierung formalisiert und einige Beweise dafür geliefert, dass er nicht relativiert. Um Ihre erste Frage teilweise zu beantworten, zeigen ihre Ergebnisse, dass einige Klassentrennungsbeweise nicht auf einer starken Diagonalisierung beruhen können. Hier ist die Zusammenfassung:

Wir definieren und untersuchen eine starke Diagonalisierung und vergleichen sie mit einer schwachen Diagonalisierung, die in [7] impliziert ist. Kozens Ergebnis in [7] zeigt, dass praktisch jede Trennung als schwache Diagonalisierung neu formuliert werden kann. Wir zeigen, dass es Sprachklassen gibt, die nicht durch starke Diagonalisierung getrennt werden können, und liefern den Beweis, dass eine starke Diagonalisierung nicht relativiert. Wir definieren auch zwei Arten der indirekten Diagonalisierung und untersuchen ihre Kraft.

Da wir eine starke Diagonalisierung in Bezug auf universelle Sprachen definieren, untersuchen wir deren Komplexität. Wir unterscheiden und vergleichen schwache und strenge universelle Sprachen. Schließlich analysieren wir einige scheinbar schwächere Varianten universeller Sprachen, die wir pseudouniversale Sprachen nennen, und zeigen, dass sie unter schwachen Schließbedingungen leicht universelle Sprachen ergeben.

1-Nash, A., Impagliazzo, R., Remmel; J. "Universelle Sprachen und die Kraft der Diagonalisierung." 18. IEEE-Jahreskonferenz über Computerkomplexität (CCC'03), p. 337, 2003.

Mohammad Al-Turkistany
quelle
5

Gibt es Klassentrennungsbeweise, die nicht auf Diagonalisierung basieren?

Ja, aber nicht für einheitliche Komplexitätsklassen. Wir haben kein Argument, um solche Beweise auszuschließen, aber bisher scheinen alle Trennungen zwischen einheitlichen Komplexitätsklassen an irgendeiner Stelle eine Diagonalisierung zu verwenden.

Können wir einen Selbstreferenzmechanismus dahinter finden?

Ich denke nicht, dass die ungleichmäßigen Klassentrennungen in "Selbstreferenz" -Argumente umgewandelt werden können, da sie keine einheitlichen Klassen sind und nicht aufgezählt werden können. Für ein Selbstreferenzargument müssen wir die Mitglieder der Klasse aufzählen.

Hat jede Klassentrennung einen "kanonischen natürlichen" Beweis (im informellen Sinne)?

Kommt darauf an, was du mit "kanonisch" meinst. AFAIK, es gibt keinen Konsens über die Antworten auf die Frage "Wenn zwei Beweise im Wesentlichen identisch sind?".

Wenn ja, sollten wir versuchen, nicht relativierende Argumente zu finden, anstatt andere Beweisschemata für offene Fragen. Kann jeder nicht diagonale Beweis in einen diagonalen umgeschrieben werden?

Wie andere bereits betont haben, hängt die Antwort davon ab, was Sie unter einer Diagonalisierung verstehen. Im allgemeineren Sinne (Kozens Artikel, der von Lance verlinkt wurde) lautet die Antwort Ja für zwei verschiedene "Komplexitätsklassen" (wie in Kozens Artikel definiert). Sie können das Argument in ein "Diagonalisierungs" -Argument umwandeln. Aber:

  1. Dies gilt nicht für Komplexitätsklassen, die die in Kozens Artikel angegebenen Anforderungen nicht erfüllen (dh keine Kozen- "Komplexitätsklassen" sind).
  2. PPSpace
  3. Das Wichtigste ist, dass je allgemeiner eine Methode ist, desto eingeschränkter ihre Anwendungen sind (wenn sie selbst verwendet wird), da die Methode für mehr Fälle funktionieren muss und dies eine Einschränkung der Methode darstellt, können wir die spezifische nicht verwenden Informationen, die wir über das Problem haben, wenn es nicht geteilt wird oder nicht durch etwas Ähnliches für andere Probleme ersetzt werden kann, auf die wir die Methode anwenden möchten.
  4. Wir können die Trennungsargumente in "Diagonalisierungs" -Argumente umwandeln (unter Berücksichtigung der oben erwähnten Einschränkung), aber die Tatsache, dass "die Diagonalisierungsfunktion die Klassen wirklich trennt" selbst einen Beweis benötigt. Kozen Papier zeigen , dass es existiert eine Diagonalisierung Funktion , wenn die Klassen unterschiedlich sind, aber wie können wir wissen , dass eine gegebene Funktion ist wirklich Diagonalisierung? Wir brauchen einen Beweis! Und das Papier (AFAIU) gibt uns keine Vorstellung davon, wie wir diese Beweise finden können. Wenn wir ein Trennungsargument haben, können wir es in einen Diagonalisierungsbeweis verwandeln, aber das ist erst danacheinen Beweis haben. Der ursprüngliche Proof dient als Teil des neuen Diagonalisierungsnachweises und zeigt, dass die Funktion wirklich diagonalisiert. (Und in gewissem Sinne wird der aus Kozens Papier konstruierte Diagonalisierungsbeweis nicht "kanonisch" sein, da er vollständig vom ursprünglichen Argument abhängt.)
Kaveh
quelle
Ich sollte bei Ihrer zweiten Frage (Können wir einen Selbstreferenzmechanismus dahinter finden?) Und der Ungleichmäßigkeit vorsichtiger sein. Ich denke, Sie müssen genauer sagen, was Sie unter "Selbstreferenzmechanismus" verstehen. Das Wort "Selbstreferenz" ist eines der Wörter, die häufig missbraucht werden (insbesondere in philosophischen Werken), daher sollten wir vorsichtig sein. Der übliche Selbstreferenzmechanismus (im Sinne von Godel siehe auch R. Smullyans Buch "Diagonalization and Self-Reference", 1994) erfordert die Aufzählung der Objekte (hier TMs) der kleineren Klasse in der Sprache. Aber es gibt andere, die auch verwenden
Kaveh
Verwenden Sie das Wort "Selbstreferenz". EgK Mulmuley verwendet es in der uneinheitlichen Umgebung seines GCT in dem, was er als "Selbstreferenzparadoxon" bezeichnet. Aber es ist schwer für mich zu sehen, ob Sie daran denken, wenn Sie einen "Selbstreferenzmechanismus" verwenden.
Kaveh