Unmöglichkeit in Berechenbarkeit und Komplexität: immer letztendlich aufgrund diagonaler Argumente?

8

Wenn wir in der Berechenbarkeit beweisen wollen, dass ein Problem nicht rekursiv oder nicht rekursiv aufzählbar ist, können wir z. B. Reduktionen aus anderen nicht rekursiven oder nicht re-Problemen, dem Riceschen Theorem, dem Rice-Shapiro-Theorem usw. verwenden. Diese Techniken funktionieren dank oder basieren direkt auf der Existenz eines diagonalen Arguments (dh ein Programm verhält sich umgekehrt wie sein Eingabeprogramm M ' , so dass M = M ' widersprüchlich ist). Wenn wir in der Komplexität beweisen wollen, dass ein Problem in einiger Zeit nicht berechnet werden kann (unabhängig von unbewiesenen Behauptungen wie z. B. P N P.MMM=MPNP) verwenden wir Argumente, die letztendlich auf einem diagonalen Argument basieren (z. B. beweist der Satz der Zeithierarchie, dass vollständige Probleme nicht in P vorliegen , sondern dass der Satz auch durch Verwendung eines diagonalen Arguments bewiesen wird).EXPTIMEP

Meine Frage lautet also wie folgt. Sind alle wichtigen Unmöglichkeitsergebnisse in Bezug auf Berechenbarkeit und Komplexität (tatsächliche Unmöglichkeit, nicht Unmöglichkeit bis zu einem unbewiesenen Ergebnis) letztendlich auf ein diagonales Argument zurückzuführen? Das heißt, kommt all unser wichtiges "Unmöglichkeitswissen" in Bezug auf Berechenbarkeit und Komplexität von der Tatsache, dass Programme leistungsfähig genug sind, um Programme auszuführen?

Das einzige wichtige Unmöglichkeitsergebnis, das mir in den Sinn kommt und das letztendlich nicht auf einem diagonalen Argument beruht, ist, dass die Ackermann-Funktion nicht primitiv rekursiv ist. Vermisse ich andere wichtige Gegenbeispiele dieser offensichtlichen "Regel"?

EDIT (18. November): Es tut mir leid, dass meine Frage sich besonders auf das diagonale Argument selbst konzentriert hat, aber ich interessiere mich mehr für alle Argumente, die auf der Selbstreferenz von Programmen beruhen (einschließlich des diagonalen Arguments, des Berry-Paradoxons usw.). Für einfachere Sprachen (z. B. regulär oder kontextfrei) haben wir "strukturelle" Unmöglichkeitsargumente, die darauf basieren, wie diese Sprachen aufgebaut sind (z. B. Pumping Lemmas). Bei rekursiven oder re-Sprachen hängen die meisten Unmöglichkeitsergebnisse jedoch stark von der Selbstreferenz der Programme ab. Das habe ich gemeint.

EXPTIME-vollständig
quelle
Eigentlich ist der Beweis, dass die Ackerman-Funktion nicht pr ist, eine ziemlich klassische Anwendung der Diagonalmethode!
Cody
1
Außerdem: Mögliches Duplikat von cstheory.stackexchange.com/questions/6575/…
cody
1
Ja, es gibt ein verstecktes diagonales Argument im Beweis, dass sich eine Funktion möglicherweise nicht selbst verschlimmert
cody
1
Wahrscheinlich stammen einige Ergebnisse aus dem Pigeonhole-Prinzip: Kolmogorovs Komplexität fällt mir ein ("einige Saiten sind nicht komprimierbar ..."). Ich wette 1 $, dass alle negativen Ergebnisse "über eine endliche Domäne" die PP an ihrer Wurzel haben :-D :-D
Marzio De Biasi
3
Die unteren Grenzen der Schaltungs- und Formelkomplexität werden mit völlig anderen Techniken wie zufälligen Einschränkungen und dem Schalt-Lemma oder der Kommunikationskomplexität über Karchmer-Wigderson-Spiele
Sasho Nikolov

Antworten:

7

Untergrenzen in ungleichmäßigen Berechnungsmodellen wie Booleschen Formeln und Schaltkreisen werden mit kombinatorischen Argumenten bewiesen. Einige Beispiele sind Krapchenkos Methode unter Verwendung formaler Komplexitätsmaße, Razborovs Approximationsmethode für monotone Schaltkreise, die Zufallsbeschränkungsmethode, einschließlich Zufallsbeschränkung + das Schalt-Lemma, und Tiefenuntergrenzen unter Verwendung der Kommunikationskomplexität über Karchmer-Wigderson-Spiele. Zu diesem Material finden Sie unter anderem Vorlesungsunterlagen von Sudan , Kopparty , Buss , Zwick .

Sasho Nikolov
quelle
Persönliche Lieblingsantwort, ich habe viel gelernt, danke. Davids und Marzios sind auch gute Antworten.
EXPTIME-abgeschlossen
9

Die Untergrenze des Standardvergleichsmodells für die Sortierung und die Untergrenzen des meisten Zellsondenmodells für Datenstrukturen sind bedingungslos (für die Berechnung innerhalb des Modells, aber Sie können dasselbe über die Untergrenzen der Turing-Maschine sagen) und hängen eher von der Informationstheorie als von der Diagonalisierung ab.

David Eppstein
quelle
2
Es gibt auch Unmengen von informationstheoretischen bedingungslosen Untergrenzen für verschiedene Modelle des verteilten Rechnens und des parallelen Rechnens. Auch dort keine Diagonalisierung.
Jukka Suomela
3

Ein Werkzeug, mit dem negative / Unmöglichkeitsergebnisse nachgewiesen werden können, ist die Inkompressibilitätsmethode :

cyAmm(12c)+1XC(xy)logmc

O(n2){wwR}anbn

Letztendlich stützt sich der obige Satz auf das Taubenprinzip, das selbst einige nette direkte Anwendungen hat; zum Beispiel:

d>0d

dd

Marzio De Biasi
quelle
Es gibt auch einen schönen Beweis für die Unmöglichkeit, dass es nur endlich viele Primzahlen gibt :). (Und schätzt die Größe der n-ten Primzahl korrekt auf einen log n-Faktor.)
Joshua Grochow
1
n0nn0K(n)log2(n)n=ab
1

Tatsächlich kann das Halteproblem ohne Verwendung von Diagonalisierung bewiesen werden. (Und jeder gültige ZFC-Satz hat einen ZFC-Beweis, der Diagonalisierung verwendet ... denken Sie darüber nach.)

Der Beweis verwendet das Berry-Paradoxon und geht wie folgt vor:

Indizieren Sie alle Turing-Maschinen in angemessener Weise. Nehmen Sie im Widerspruch an, dass das Halteproblem gelöst werden kann. Dann betrachten Sie diesen Algorithmus:

f (N) gibt die am wenigsten indizierte Turingmaschine zurück. X st X (X) hält nicht an und X ist nicht die Ausgabe einer Turingmaschine M und die Eingabe I unter N Zeichen (dh M (I) gibt X -> aus | M | + | I |> = N).

Nun wählen wir ausreichend groß N st f (N) muss eine Beschreibung von X zurückgeben, die genau durch die Berechnung von f (N) beschrieben wird. Wenn f berechenbar ist, dann ist M = f und I = N. Zum Beispiel könnten wir N = ein Googol (10 ^ 100) lassen.

Dies legt nahe, dass f (N) keine Gesamtfunktion ist, da für f (10 ^ 100) keine zufriedenstellende Ausgabe vorliegt. Dies widerspricht der Annahme, dass das Halteproblem gelöst werden kann. Betrachten Sie den folgenden Pseudocode (der weit weniger als 10 ^ 100 Zeichen beträgt, wenn er in C ++ zu echtem Quellcode erweitert oder sogar als Turing-Maschine geschrieben wird) für f:

f (N)

{

für (int i = 1 ;; i ++)

{

  if (simulate DoesHalt(UTM(i,i)) == false)

  {

         (simulate all machines and inputs M(I) with |M|+|I|<N)

         if all such inputs do not output i

                 return i;

  }

}}

}}

Es ist klar, dass alle Eingaben angehalten werden und ordnungsgemäß funktioniert, vorausgesetzt, dass das Anhalten des Problems gelöst werden kann. Durch das oben Gesagte haben wir, dass das Halteproblem nicht gelöst werden kann.

Dieser Beweis verwendet keine Form der Diagonalisierung. In der Tat sollten Sie einen Blick auf meine Frage werfen:

Ist eine Definition des Wortes Paradoxon "etwas, das verwendet werden kann, um das Problem des Stillstands als unentscheidbar zu beweisen?"

... für eine Diskussion der Tatsache, dass viele Paradoxe anstelle des Lügnerparadoxons oder des Russellschen Paradoxons verwendet werden können, um zu beweisen, dass das Halteproblem nicht gelöst werden kann. Einige dieser nicht diagonalen Argumentparadoxe umfassen das unerwartete hängende Paradoxon und (wie gerade beschrieben) das Beerenparadoxon.

Philip White
quelle
1
Dies bedeutet, dass f (N) genau das ist, was ich in der Beschreibung beschrieben habe, wie f Funktionen berechnet. Lesen Sie den Wikipedia-Artikel zum Berry-Paradoxon, wenn Sie dies verwirrt (oder stellen Sie in den Kommentaren weitere Fragen). Ich wollte "i" anstelle von "X" schreiben und werde das in Kürze beheben. Und ja, meine wortreiche Formulierung von "X ist nicht die Ausgabe eines M" könnte vereinfacht werden, wie Sie vorschlagen. Abgesehen von diesen kleinen Punkten hoffe ich, dass Sie zustimmen, dass meine Antwort richtig ist. Ich werde gleich auf Ihren anderen Kommentar eingehen.
Philip White
2
Was unbeantwortet zu bleiben scheint, an dem das OP interessiert war, vielleicht passend für eine separate Frage, ist, ob wir Selbstreferenz vollständig vermeiden können.
Kurt Mueller
2
Ich glaube, ich stimme den anderen zu: Die Essenz des Berry-Paradoxons ist immer noch dieselbe wie die Essenz der Cantor-Diagonalisierung. Siehe z. B. cstheory.stackexchange.com/q/21917/129 , cstheory.stackexchange.com/q/2853/129 , cstheory.stackexchange.com/q/37824/129 .
Joshua Grochow
2
AA×Ae:A×AB
2
e:ABeBBeBBXX,XX(X). Es geht nicht um Selbstreferenzialität, sondern nur darum, dasselbe Objekt zweimal auf zwei verschiedenen "semantischen" Ebenen zu verwenden.
Damiano Mazza