P = NP, was wäre wenn "philosohpiestunde"

[ZuseZ3]

Und gleich mal im Titel vertipt
Naja, ich schätze mal hier passt das ganze am ehsten rein...
Da ich demnächst einen Vortrag über NP vollständigkeit, genauer gesagt das Färbeproblem im Unterricht halten werde und es wird garantiert die Frage kommen wird was wäre wenn doch P = NP gilt (und es sich um ein Polynom mit niedrigem exponenten handelt).
Daher wollte ich einfach mal nach ein paar konkreten Beispielen Fragen.
So im groben ist es mir ja klar, nur wäre es schön ein paar sehr konkrete Beispiele aufzählen zu können.
Daher wäre ich dankbar wenn ihr einfach mal die eurer Meinung nach spannendsten Folgen aufzählen würdet.
Natürlich wären die bekannten NP vollständigen Optimierungsprobleme "direkt" lösbar aber da es dafür mehr oder weniger gute Optimierungen gibt wäre das ja nur eine relative Verbesserung, a la: einen 5% besseren Empfang haben, weil die Funkmasten jetzt endlich optimal angeordnet sind.
(Und ich weiß endlich was ich noch in meinen Rucksack packen muss )

Hier, was mir als große änderung so spontan eingefallen ist:
-(Asymetrische) Kryptographie währe nutzlos
....

 

[HominiLupus]

https://www.google.de/search?q=p=np+consequences

Davon z.B. http://programmers.stackexchange.com/questions/148836/what-would-be-the-impact-of-p-np

Ist Google so schwer?

 

[Mr.Smith]

kryptographie ist es sinnlos^^ fbi zwingt einfach den hersteller das zu umgehen^^

 

[SoDaTierchen]

NP vollständige Probleme sind auch heute schon "direkt" lösbar, die Zeit für allgemeine Probleme ist nur exorbitant hoch, wenn die Versuchsgröße groß wird.

P = NP würde nichts anderes Bedeuten, als dass die Verifikation einer Lösung in ähnlicher Zeit wie die Konstruktion einer Lösung stattfinden kann. Auf sowas wie Funk-Empfang wird das wenig Einfluss haben, die werden nach wirtschaftlichen Aspekten gesetzt, nicht für optimale Netzabdeckung. Wobei eine optimale Lösung ohnehin nicht möglich ist, da sich durch Bewegung von mobilen Empfängern die Ausgangslage ohnehin ständig ändert.

Das größte Problem wird in der Kryptographie gesehen. Dort wird ein Großteil der verwendeten kryptografischen Verfahren hinfällig, wenn die Zeit ein Passwort zu bestätigen sehr ähnlich der Zeit wird, ein gültiges Passwort zu finden. Allerdings hebelt das nicht alle kryptografischen Verfahren aus, denn es gibt eine handvoll Verfahren, die sich davon wenig beeindrucken lassen (z.B. one-time pad, carter-wegman).

ABER! Und jetzt kommt das große Aber: Es hängt auch davon ab, wie effizient die gefundene Lösung dann ist. Handelt es sich um einen nicht-konstruktiven Beweis für P=NP, dann ändert sich erstmal gar nichts, weil kein Algorithmus bekannt ist, der das auch umsetzt. Und selbst ein konstruktiver Beweis muss lediglich die obere Schranke O(n^k) erfüllen. Ist k allerdings eine große Zahl, z.B. 100, dann bringt auch dieser Algorithmus nichts - er würde schlicht zu lange dauern. Also es muss sich durch diesen Beweis nicht zwingend etwas ändern.

Was aber definitiv eine Folge wäre: Der Entdecker von P=NP würde als mathematischer Held gefeiert und vom Clay Mathematics Institute mit einer Million US-Dollar belohnt werden

 

[asdfman]

Welche fundamentalen Probleme der Kryptographie sind denn NP-vollständig? Das Faktorisierungsproblem meines Wissens nicht. Das diskrete Logarithmusproblem auch nicht. RSA-Problem? Diffie-Hellman-Problem?

https://en.wikipedia.org/wiki/Compu...ems_in_NP_not_known_to_be_in_P_or_NP-complete

€: Das Merkle-Hellman Kryptosystem basiert auf dem NP-vollständigen Teilsummenproblem, konnte aber trotzdem erfolgreich angegriffen werden. Deshalb zählt das für mich hier nicht.

Dann gibt es noch asymmetrische Kryptosysteme, die nicht auf zahlentheoretischen Problemen beruhen, z.B. McEliece. Darauf hätte die Frage, ob P=NP überhaupt keinen Einfluss.

 

[ZuseZ3]

es wird garantiert die Frage kommen wird was wäre wenn doch P = NP gilt (und es sich um ein Polynom mit niedrigem exponenten handelt).
....

Das das ganze sowieso unwahrscheinlich ist habe ich oben btw. bereits geschrieben, genauso wie es nur bedeutsam ist wenn es keine sehr hohen unteren Schranken für die Polynomialzeitalgorithem gibt.

@Homi, ist freundlich sein so schwer? Für meine Note ist es volkommen egal wie "beeindruckend" die vorgestellten Folgen sind, es geht mir eher darum das ganze nicht ganz so trocken zumachen, vieleicht erwägt der ein oder andere dann ja später ein it Studium.
Wenn du nicht miträtseln magst zwingt dich hier aber auch keiner dazu.
Optimal wären wohl Beispiele für Problemlösungsansätze, die zurzeit bekannt sind, aufgrund des aktuell exp Rechenaufwandes aber nicht praktisch einsetzbar sind.

AIs gehen immerhin schonmal in die Richtung, sie werden zwar genutzt, würden wenn man effizient die optimalen Trainingsdaten aus einer Menge fischen könnte aber wohl deutlich schneller lernen.
Der Unterschied dürfte daher deutlich spürbar sein.

 

[SoDaTierchen]

@asdfman: Zu behaupten, Kryptografie hat nichts mit P=NP zu tun, widerspricht irgendwie der Meinung von allen, die etwas davon verstehen Nur weil ein Problem oder Algorithmus bisher nicht als NP-vollständig klassifiziert wurde, heißt es nicht, dass die Lösung von P=NP keinen Einfluss darauf hat. P=NP bezieht sich eben auch nicht nur auf NP-Vollständigkeit, sondern auf NP im allgemeinen. Jedes nichtdeterministisch-polynomielle Problem wäre davon betroffen.

Eventuell einfacher ausgedrückt (auch für andere die das hier lesen und nicht so tief drin stecken): P heißt, ein Problem kann in polynomieller Zeit gelöst werden (unter Umständen sehr lange, in der Theorie aber als "in vertretbarer Zeit lösbar" eingestuft). NP heißt, ein Problem kann nicht-deterministisch in polynomieller Zeit gelöst werden. Nichtdeterminismus heißt, es ist nicht an jedem Schritt der Berechnung klar, welcher Schritt als nächstes folgt, aber es gibt an diesem Punkt eine Menge von Schritten, von denen mindestens einer zum Ziel führt. Also könnte man auch sagen: Probleme in P lassen sich berechnen, Probleme in NP lassen sich erraten. Und GENAU darauf basiert Kryptografie. Wer die Schlüssel kennt, kann die Nachricht errechnen (in P berechnen), wer sie nicht kennt, müsste die Nachricht erraten (in NP berechnen).

Ebenso gilt aber auch: P=NP bedeutet eben nicht zwingend, dass Kryptografie unbrauchbar würde. Es hängt auch davon ab, wie es bewiesen werden würde. Nur weil die Lösung dann nicht mehr nichtdeterministisch wäre, heißt das nicht, dass sie in sinnvoller Zeit berechenbar ist.

Vielleicht ein wenig für dich zum lesen:
NP (Komplexitätsklasse)
Einführung in die Kryptographie (TU München)

 

[crvn075]

Ebenso gilt aber auch: P=NP bedeutet eben nicht zwingend, dass Kryptografie unbrauchbar würde. Es hängt auch davon ab, wie es bewiesen werden würde. Nur weil die Lösung dann nicht mehr nichtdeterministisch wäre, heißt das nicht, dass sie in sinnvoller Zeit berechenbar ist.

Das ist zwar richtig. Aber wenn man einmal an dem Punkt sein sollte, an dem jemand mit irgend einem unbrauchbaren da zu großen, aber eben doch existierenden O(n^k) um's Eck kommt, dann würde das imho trotzdem eine neue Unsicherheit hervorrufen, die unsere Sicht auf Verschlüsselung definitiv verändern würde.

Aber man sollte nicht nur negative Dinge Anführen. Ich fände es cool, wenn man in Zukunft das Optimum schwieriger Probleme deterministisch und effizient finden könnte. Zwar wurde schon angemerkt, dass es für viele Problemstellungen gute approximative Verfahren gibt, aber alleine eine gute Parametrisierung für viele dieser Algorithmen zu finden kann schon nervig sein. Im Studium mussten wir mal einen genetischen Algorithmus für das TSP mit 180 Städten entwickeln (zur Veranschaulichung: es gibt ca. 5*10^326 verschiedene Lösungen, also eine Zahl mit 327 Stellen). Nach ewiger Kalibrierung lief der Algo dann ein paar hundert mal durch. Wenn er die "Best known Solution" fand oder max. 5% von dieser weg war, dann tat er das in (für mich) beeindruckenden 70 Sekunden. In den nächsten Dutzend Durchlaufen kam er diesem Ergebnis trotz gleicher Parameter aber nicht mehr annähernd nahe, bis es dann irgendwann endlich wieder soweit war. Frustierend war auch die Erkenntnis, dass die gefundenen Parameter für den Algorithmus für andere TSPs wertlos waren und wieder neu gefunden werden mussten.