Gibt es kontraproduktive Ergebnisse in der theoretischen Informatik?

30

Einige mathematische und logische Paradoxe könnten wahrscheinlich automatisch auf Computer angewendet werden. Gibt es jedoch Paradoxe, die in der Informatik selbst entdeckt wurden?

Mit Paradoxen meine ich kontraintuitive Ergebnisse, die wie ein Widerspruch aussehen.

Serg
quelle
2
Suchen Sie nach Dingen, die sich paradox oder uneinheitlich anfühlen (z. B. Russells Paradoxon)?
Raphael
2
Ich kenne kein passendes Tag für diese Frage, vielleicht [großes Bild] oder [weiche Frage]. Können Sie ein Beispiel für die von Ihnen erwähnten mathematischen Paradoxien nennen, damit wir wissen, wovon Sie sprechen?
Kaveh
2
Offensichtlich gibt es keine bekannten Inkonsistenzen in der Informatik - das wäre besorgniserregend. Suchen Sie nur nach kontraproduktiven Ergebnissen? Sind Ergebnisse wie der PCP-Satz, der Rekursionssatz von Kleene und Kryptosysteme mit öffentlichem Schlüssel bizarr genug, um für Sie als Paradox zu gelten?
Thomas
4
@serg, es wäre sehr hilfreich, wenn du antworten könntest, um deine Frage zu klären. Entweder meinst du deine Frage in einem sehr "sanften" Sinne, den Thomas vorschlägt - in diesem Fall ist die Frage richtig als großes Bild markiert und meine Antwort unten ist nicht themenbezogen, oder du meinst sie in einem etwas technischen Sinne ("Anwendungen und Auswirkungen logischer Paradoxe in der Informatik "). In diesem Fall sollte Ihre Frage mit lo.logic und nicht mit big picture gekennzeichnet werden. Oder du meinst etwas ganz anderes, das wir vier Kommentatoren nicht erraten haben!
Rob Simmons
4
Gegenintuitivität ist eine Funktion der Zeit. Die Tatsache, dass so viele verschiedene Fragen alle NP-vollständig sind, war vor Karps Artikel zweifellos kontraproduktiv, ebenso wie die Tatsache, dass Kanäle vor Shannons bestimmte Informationskapazitäten haben. Heute sind die Menschen jedoch an diese Ergebnisse gewöhnt.
Peter Shor

Antworten:

28

Ich finde die Tatsache, dass der Netzwerkfluss ein polynomieller Zeitzähler ist, intuitiv. Auf den ersten Blick scheint es viel schwieriger zu sein als viele NP-harte Probleme. Oder anders ausgedrückt, es gibt viele Ergebnisse in CS, bei denen die Laufzeit zur Lösung der Probleme viel besser ist als erwartet.

Sariel Har-Peled
quelle
6
dito: Ich habe die Studenten dazu bringen lassen, die Nicht-Intuitivität des Netzwerkflusses zu kommentieren, und selbst die Tatsache, dass Übereinstimmungen in Polyzeit durchgeführt werden können, scheint höchst überraschend.
Suresh Venkat
9
Da stimme ich nicht ganz zu Der Netzwerkfluss kann leicht auf lineare Programmierung reduziert werden. Sie behaupten also, dass lineare Programmierung in P nicht intuitiv ist. Vielleicht. Aber Dualität zeigt, dass LP in NP und Co-NP ist, was zumindest nahelegt, dass es nicht so schwer sein kann. Weniger intuitiv ist, dass min-cut in P lösbar ist, weil es natürlich kein "fraktioniertes" Problem ist.
Chandra Chekuri
21

P=NPEXPP/polyNEXPACC

Suresh Venkat
quelle
Bitte geben Sie das Ergebnis von Meyer an.
Mohammad Al-Turkistany
1
Ich weiß nicht, ob es einen direkten Bezug gibt. Das Karp-Lipton Paper ( faculty.cs.tamu.edu/chen/courses/637/2008/pres/ashraf.pdf ) schreibt Meyer dieses Ergebnis zu, aber es gibt kein Zitat.
Suresh Venkat
20

SAT hat nur dann einen Polynom-Zeit-Algorithmus, wenn P = NP ist. Wir wissen nicht, ob P = NP ist. Ich kann jedoch einen Algorithmus für SAT aufschreiben, der polynomial ist, wenn P = NP wahr ist. Ich kenne den korrekten Verweis dafür nicht, aber die Wikipedia-Seite gibt einen solchen Algorithmus an und schreibt Levin gut.

mikero
quelle
5
In ähnlicher Weise haben wir einen nachweislich optimalen Algorithmus für das Factoring, der in Polynomzeit abläuft, wenn das Factoring in P ist, aber wir wissen nicht, ob das Factoring in P ist (oder wie die Laufzeit dieser optimalen Funktion analysiert wird).
Ross Snider
9
Dies wird normalerweise als "Levin-Universalsuche" bezeichnet, und die korrekte Referenz lautet: L. Levin, Probleme mit der universellen Aufzählung. Probleme der Informationsübertragung, 9 (3): 265-266, 1973 (aus dem Russischen übersetzt). Dies ist das gleiche Papier, in dem Levin die NP-Vollständigkeit eingeführt hat (siehe auch Cook & Karp, aber meines Wissens hat keiner von beiden den Begriff eines optimalen universellen Suchalgorithmus eingeführt). Die englische Übersetzung ist in Trakhtenbrots berühmter Umfrage zu finden: doi.ieeecomputersociety.org/10.1109/MAHC.1984.10036
Joshua Grochow
18

Die meisten Studenten sind von der Berechenbarkeit begeistert. Ein schönes Beispiel mit hoher Verwirrungsrate ist folgendes:

f(n):={1,π has 0n in its decimals0,else

f

f

Raphael
quelle
7
Dies scheint mir eines dieser Probleme zu sein, bei denen all seine Tricks so sind, wie es heißt. Dies erinnert mich ein wenig daran, einen Algorithmus zu nehmen, nämlich dass n eine Konstante ist und zu proklamieren, dass der Algorithmus jetzt in konstanter Zeit abläuft. Die schwierige Frage, die sich die Leute normalerweise stellen, ist, ob wir ein Programm schreiben können, das entweder beweist, dass pi eine 0 ^ n-Zeichenfolge für alle n enthält oder das größte n bestimmt, für das es wahr ist.
Joseph Garvin
4
Sicher, aber die Tatsache, dass sie so denken, zeigt nicht, wie schwierig die Formulierung der Funktion ist, sondern dass die Menschen den Unterschied zwischen Existenz und Konstruktion nicht verstehen.
Raphael
18

IP=PSPACE

Wie Arora & Barak es ausdrückten (S. 157) "Wir wissen, dass Interaktion allein uns keine Sprachen außerhalb von NP gibt. Wir vermuten auch, dass Randomisierung allein der Berechnung keine signifikante Kraft hinzufügt. Wie viel Kraft könnte also die Kombination von Randomisierung und Interaktion bieten? "

Anscheinend ziemlich viel!

Huck Bennett
quelle
13

Wie Philip sagte, ist der Satz von Rice ein gutes Beispiel: Bevor man die Berechenbarkeit studiert, muss man wissen, dass es etwas gibt, das man über Berechnungen berechnen kann. Es stellt sich heraus, dass wir nur über einige Berechnungen etwas berechnen können.

Max
quelle
13

Wie wäre es mit Martin Escardos Veröffentlichungen, die zeigen, dass es unendlich viele Mengen gibt, die in endlicher Zeit erschöpfend durchsucht werden können? Siehe Escardos Gast-Blogeintrag in Andrej Bauers Blog, zum Beispiel "Scheinbar unmögliche Funktionsprogramme" .

Dominic Mulligan
quelle
12

Das Rekursions-Theorem scheint sicherlich nicht intuitiv zu sein, wenn Sie es zum ersten Mal sehen. Im Wesentlichen heißt es, dass Sie bei der Beschreibung einer Turing-Maschine davon ausgehen können, dass sie Zugriff auf eine eigene Beschreibung hat. Mit anderen Worten, ich kann Turingmaschinen bauen wie:

TM M akzeptiert n, wenn n ein Vielfaches der Häufigkeit ist, mit der "1" in der Zeichenfolgendarstellung von M angezeigt wird.

TM N nimmt eine Zahl n auf und gibt n Kopien von sich aus.

Beachten Sie, dass sich die "Zeichenfolgendarstellung" hier nicht auf die informelle Textbeschreibung bezieht, sondern auf eine Codierung.

Mark Reitblatt
quelle
11

Ein weiteres kontraintuitives Ergebnis ist die Überprüfung informationstheoretischer Ergebnisse auf der Grundlage komplexitätstheoretischer Annahmen. Zum Beispiel haben Bellare et al. In ihrer Arbeit Die (wahre) Komplexität des statistischen Nullwissens hat konstruktiv bewiesen, dass unter der zertifizierten Annahme eines diskreten Protokolls jede Sprache, die statistisches Nullwissen von einem ehrlichen Prüfer zulässt, auch statistisches Nullwissen zulässt.

Das Ergebnis war so merkwürdig, dass es die Autoren überraschte. Sie wiesen mehrmals auf diese Tatsache hin; Zum Beispiel in der Einleitung:

Angesichts der Tatsache, dass statistisches Nullwissen ein rechnerunabhängiger Begriff ist, ist es etwas seltsam, dass Eigenschaften darüber unter der Annahme der rechnerischen Unlösbarkeit bewiesen werden könnten.

PS: Ein stärkeres Ergebnis wurde später von Okamoto ( Über Beziehungen zwischen statistischen Null-Wissens-Beweisen ) bedingungslos bewiesen .

Beschreibung einiger Begriffe

Da das obige Ergebnis viel kryptografische Fachsprache enthält, versuche ich, jeden Begriff informell zu definieren.

  1. pp1
  2. Nullwissen : Ein Protokoll, das polynomzeitbegrenzten Parteien kein Wissen liefert.
  3. Statistisches Nullwissen: Ein Protokoll, das selbst für rechnerisch unbegrenzte Parteien keine Informationen liefert, außer mit vernachlässigbarer Wahrscheinlichkeit.
  4. Honest-Verifier-Zero-Knowledge: Ein Protokoll, das polynomialzeitgebundenen Parteien kein Wissen liefert, wenn sie wie im Protokoll angegeben vorgehen.
MS Dousti
quelle
11

Wie wäre es mit der Tatsache, dass Computing Permanent # P-Complete ist, aber eine Determinante für Computing - eine Art seltsame Operation, die zufällig in der Klasse NC liegt?

Das scheint ziemlich seltsam zu sein - es musste nicht so sein (oder vielleicht war es so ;-))

Akash Kumar
quelle
7

Das lineare Programmierproblem ist in (schwach) polynomieller Zeit lösbar. Dies scheint sehr überraschend: Warum könnten wir einen unter einer exponentiellen Anzahl von Eckpunkten eines hochdimensionalen Polytops finden? Warum könnten wir ein Problem lösen, das so lächerlich aussagt?

Ganz zu schweigen von den linearen Programmen mit Exponentialgröße, die wir mit der Ellipsoidmethode und den Trennungs-Orakeln und anderen Methoden (Hinzufügen von Variablen usw.) lösen können. Es ist zum Beispiel erstaunlich, dass eine LP mit einer exponentiellen Anzahl von Variablen wie der Karmakar-Karp-Relaxation von Bin Packing effizient approximiert werden kann.

Sasho Nikolov
quelle
2
Die Tatsache, dass es eine exponentielle Anzahl von Lösungen gibt, gibt es nicht nur bei LP. Die meisten diskreten Optimierungsprobleme haben die gleiche Funktion, aber sie haben Poly-Time-Algorithmen, nicht wahr? LP ist ein Spezialfall der konvexen Optimierung, bei dem ein lokales Optimum ein globales Optimum ist. Wir können auch konvexe Optimierungsmodule und Epsilon-Probleme aufgrund von Irrationalität und anderen technischen Gründen lösen. Für LP kann man aufgrund der kombinatorischen Struktur von dieser kleinen Fehlerlösung zu einem Scheitelpunkt springen, der eine exakte Lösung liefert. Die Gleichwertigkeit von Trennung und Optimierung ist jedoch überraschend.
Chandra Chekuri
2
@ChandraChekuri Was ich im Sinn hatte ist, dass ein hochdimensionales geometrisches Suchproblem so klingt, als ob es schwierig sein sollte. Aber natürlich gibt es auch gute Gründe, warum es nicht so ist (Konvexität). Ich sollte stattdessen wahrscheinlich die Äquivalenz von Trennung und Optimierung betonen. Viele überraschende Konsequenzen, wie zum Beispiel das Lösen harter Optimierungsprobleme auf perfekten Grafiken.
Sasho Nikolov
3

Wenn ich Automaten unterrichte, frage ich meine Schüler immer, ob sie es überraschend finden, dass Nichtdeterminismus den Automaten mit endlichen Zuständen keine Macht verleiht (dh, dass es für jede NFA eine äquivalente - möglicherweise viel größere - DFA gibt). Etwa die Hälfte der Klassen berichtet, dass sie überrascht sind. [Ich selbst habe das "Gefühl" für das verloren, was auf der Intro-Ebene überraschend ist.]

RRE

Aryeh
quelle