Sollten wir

30

Viele Experten glauben, dass die Vermutung wahr ist, und verwenden sie für ihre Ergebnisse. Meine Sorge ist, dass die Komplexität stark von der PN P- Vermutung abhängt .PNPPNP

Meine Frage lautet also:

Kann / sollte man die Vermutung, solange sie nicht bewiesen ist, als Naturgesetz betrachten, wie im Zitat von Strassen angegeben? Oder sollten wir es als eine mathematische Vermutung behandeln, die eines Tages vielleicht bewiesen oder widerlegt wird?PNP

Zitat:

"Die Beweise für die Hypothesen von Cook und Valiant sind so überwältigend, und die Folgen ihres Scheiterns sind so grotesk, dass ihr Status vielleicht eher mit dem von physikalischen Gesetzen verglichen werden kann als mit dem von gewöhnlichen mathematischen Vermutungen."

[Volker Straßens Laudatio auf die Nevanlinna-Preisträgerin Leslie G. Valian, 1986]

Ich stelle diese Frage beim Lesen des Beitrags Physics results in TCS? . Es ist vielleicht interessant festzustellen, dass die rechnerische Komplexität Ähnlichkeiten mit der (theoretischen) Physik aufweist: Viele wichtige Komplexitätsergebnisse wurden durch die Annahme von bewiesen , während in der theoretischen Physik die Ergebnisse durch die Annahme einiger physikalischer Gesetze bewiesen werdenPNP . In diesem Sinne kann als E = m c 2 betrachtet werden . Zurück zu den Physikergebnissen in TCS? :PNPE=mc2

Könnte (ein Teil von) TCS ein Zweig der Naturwissenschaften sein?

Klärung:

(Siehe Sureshs Antwort unten)

Ist es legitim , zu sagen , dass die Vermutung in der Komplexitätstheorie ist so grundlegend wie ein physikalischen Gesetze in der theoretischen Physik (wie Strassen , sagte)?PNP

vb le
quelle
10
Die Website cstheory.stackexchange.com ist kein geeigneter Ort für Diskussionen. Bitte überprüfen Sie "Welche Art von Fragen sollte ich hier nicht stellen?" In FAQ .
Tsuyoshi Ito
11
Nun, ich hoffe, jemand könnte eine richtige Antwort auf meine Frage haben. Ich finde Strassens Sichtweise ziemlich interessant, und lustigerweise haben wir nicht darüber gesprochen. Ich werde jetzt die FAQ prüfen ...
vb le
8
Sie fragen nach der Meinung der Menschen, nicht nach Fakten, und diese Frage ist meiner Meinung nach eindeutig ungeeignet. Sie müssen nicht zustimmen, aber ich hoffe, dass meine Haltung dazu klar ist.
Tsuyoshi Ito
30
Ich denke, dass diese Frage ziemlich wichtig ist und dass wir in diesem Fall eine Ausnahme von der Tendenz machen können, Diskussionen zu vermeiden.
Gil Kalai
3
@ Gil Kalai: Es gibt viele wichtige Dinge auf dieser Welt zu besprechen, aber cstheory.stackexchange.com ist nicht der richtige Ort für sie. Besprechen Sie sie bitte woanders.
Tsuyoshi Ito

Antworten:

57

Die Aussage von Strassen muss in einen Kontext gestellt werden. Dies war eine Ansprache an ein Publikum von Mathematikern im Jahr 1986, als viele Mathematiker keine hohe Meinung von theoretischer Informatik hatten. Die vollständige Aussage ist

Für einige von Ihnen scheint es, dass die hier diskutierten Theorien auf schwachen Grundlagen beruhen. Sie nicht. Die Beweise für die Hypothesen von Cook und Valiant sind so überwältigend, und die Folgen ihres Scheiterns sind so grotesk, dass ihr Status vielleicht eher mit dem von physikalischen Gesetzen als mit dem von gewöhnlichen mathematischen Vermutungen verglichen werden kann.

Ich bin mir sicher, dass Strassen Gespräche mit reinen Mathematikern geführt hatte, die etwas in der Art von sagten

Dennoch wäre ein traditioneller Beweis von großem Interesse, und es scheint mir, dass die Hypothese von Valiant leichter zu bestätigen ist als die von Cook ...

Vielleicht würde ich es als "Arbeitshypothese" und nicht als "physikalisches Gesetz" bezeichnen.

Lassen Sie mich abschließend festhalten, dass auch Mathematiker solche Arbeitshypothesen verwenden. Es gibt eine große Anzahl von mathematischen Arbeiten, die Theoreme beweisen, deren Aussagen lauten: "Unter der Annahme, dass die Riemann-Hypothese wahr ist, dann ...".

Peter Shor
quelle
1
7
@vzn: Deshalb waren Mathematiker, die so etwas sagten, so nervig.
Peter Shor
=?
20

Ich kann drei verwandte Arten sehen, die Frage zu verstehen:

NPP

NPP

NPP

Ich denke, dass es gute Gründe gibt, auf all diese drei Fragen mit "Ja" oder "Qualifiziertes Ja" zu antworten.

Gil Kalai
quelle
11

Ich bin mir nicht sicher ob ich das verstehe. Ein physikalisches Gesetz (von der Art, die Sie angeben) ist ein mathematischer Ausdruck eines Modells (in diesem Beispiel Relativität), das behauptet, die Realität einzufangen. Ein physikalisches Gesetz kann als falsch erwiesen werden, wenn die zugrunde liegende Mathematik falsch ist, aber es kann auch falsch sein, wenn sich das zugrunde liegende Modell ändert (zum Beispiel die Newtonsche Mechanik). P vs NP ist eine spezifische mathematische Vermutung, die wahr oder falsch ist (und beweisbar ist oder nicht)

Suresh Venkat
quelle
Ich weiß, dass ich mit dem Zitat von Strassen übertreibe. Ich mache mir Sorgen, dass die Komplexität stark von der P-gegen-NP-Frage abhängt, ebenso wie die Physik von ihren Gesetzen (wie Sie geklärt haben). Die Frage ist also: Solange die P vs. NP-Vermutung nicht bewiesen ist, kann / sollte man sie als physikalisches Gesetz betrachten, wie Strassen angedeutet hat?
VB
7

So beantworten Sie Ihre ursprüngliche Frage:

PNP

"Die Annahme der NP-Härte ?: Es gibt keine physikalischen Mittel, um NP-vollständige Probleme in der Polynomzeit zu lösen."

Er hielt einen schönen Vortrag an der Universität von Waterloo mit dem Titel Computational Intractability As A Law of Physics

Mohammad Al-Turkistany
quelle
13
7
+1. Aus einem Gespräch mit einem Freund ging ich davon aus, dass das Universum keinen Grund zur Existenz haben würde, wenn P = NP.
Labotsirc
2
@labotsirc könntest du deine Gründe nennen?
T ....
5

NLPSPACENPcoNPPNP

T ....
quelle
Aus mathematischer Sicht ist Ihre Antwort sinnvoll, aber die Frage ist nicht mathematisch. Ich denke, P vs. NP ist eine natürlichere und intuitivere Frage, daher ist es nicht unvernünftig zu denken, dass P vs. NP als Ausgangspunkt geeigneter ist. Im Kern geht es meines Erachtens nicht um Mathematik, sondern darum, wie die mathematischen Berechnungsmodelle, die wir erstellt haben, der realen Welt entsprechen und was in ihr getan werden kann.
Kaveh
1
NPcoNPPNP
1

ϕϕ

Thinniyam Srinivasan Ramanatha
quelle
8
Abgesehen davon, dass wir wissen, dass P und NP gleichwertig wären, wenn physikalische Gesetze nicht die Entstehung von Blum-Shub-Smale-Maschinen in unserem Universum verhindern würden. Also die Frage ist auf die physischen Welt in diesem Sinne verwendet.
Kyle Jones
@KyleJones Entschuldigung, ich verstehe nicht, was Sie sagen (wahrscheinlich, weil ich nicht genug über das BSS-Modell weiß). Könnten Sie mir eine Referenz geben, die dies näher erläutert?
Thinniyam Srinivasan Ramanatha
Ich meinte, wenn ein mathematischer Beweis für die Aussage erbracht wird, kann kein Beweis aus der physischen Welt dies widerlegen.
Thinniyam Srinivasan Ramanatha
-4

Sie können eine Vielzahl von Experimenten mit Geschwindigkeiten und Geschwindigkeiten durchführen, und Sie erhalten überwältigende Beweise für die Validierung der Newtonschen Gesetze. Natürlich werden Sie in ganz bestimmten Experimenten einige sehr seltsame Dinge sehen, wie die Lichtgeschwindigkeit in fließendem Wasser oder einige astronomische Ereignisse. Aber Ihre überwältigenden Beweise werden Ihnen sagen: Newton hat Recht und diese Gesetze sind das, was Sie brauchen

Natürlich "hat Newton nicht Recht" und Einstein folgte ihm.

Für P = NP können wir viele Beispiele sehen, bei denen P seems NP zu sein scheint. Aber in bestimmten Fällen haben wir seltsame Dinge. Wenn P ≠ NP, gibt es eine unendliche Anzahl von Klassen zwischen ihnen, so dass wir einige Probleme in NP finden sollten, die nicht in P, aber nicht NP-vollständig sind. Wir kennen keine von ihnen, und die meisten Kandidaten waren nachweislich in P.

Was Sie über dieses Problem denken, hängt davon ab, wohin Sie schauen möchten. Es würde mich nicht wundern, wenn P = NP wäre.

Xoff
quelle
7
Tatsächlich gibt es noch viele Kandidaten für NP-Zwischenprobleme, deren genaue Komplexität ungelöst bleibt: cstheory.stackexchange.com/questions/79/…
Joshua Grochow
Diese Liste ist gut zu wissen, danke für diesen Kommentar!
Xoff