Erfasst die Diagonalisierung das Wesen der Klassentrennung?

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?

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.

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

$O$$O \subseteq \{0, 1\}^*$

$P$$NP$$P\ne NP$

$P^{PH} \subseteq IP$

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.

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. $P$$PSpace$
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.)