Was wären die realen Implikationen eines konstruktiven

56

Ich verstehe das Problem auf hohem Niveau und verstehe, dass es die Tür für die Lösung zahlreicher Probleme im Bereich der Informatik öffnen würde, wenn es sich mit einer bereitgestellten Lösung als absolut "erwiesen" herausstellen würde.P=NP

Meine Frage ist, wenn jemand einen unbestreitbaren, konstruktiven Beweis für , welche unmittelbaren Auswirkungen würden wir auf eine solche Entdeckung haben? P=NP

Ich frage nicht nach einer Meinung darüber, wie die Welt in 5-10 Jahren aussehen würde. Ich bin vielmehr der Meinung, dass dies ein so grundlegend unlösbares Problem ist, dass es die Art und Weise, wie wir rechnen, radikal verändern könnte ... viele Dinge (ja, hier zeigt sich meine Unwissenheit ...), die wir heute nicht leicht berechnen können .

Welche unmittelbare Auswirkung hätte ein gründlicher, genauer und konstruktiver Beweis von auf die Praxis?P=NP

RLH
quelle
5
Im schlimmsten Fall kann es zu keinerlei praktischen Auswirkungen kommen (außer dass die Autoren berühmt werden) - wenn der Beweis nicht konstruktiv ist, was bedeutet, dass jemand nur nachweist, dass es det gibt. Pol-Zeit-Algorithmen für die NP-vollständigen Probleme, ohne tatsächlich einen bereitzustellen.
lukas.coenig
2
In diesem hypothetischen Szenario muss ich am liebsten berücksichtigen, dass die Optimierung einfach wird. Ein spezieller Fall wäre, dass das Finden von Parametern, die globale MLEs für jedes probabilistische Modell sind, trivial wäre. Dies würde beispielsweise Forscher in der Genetik und anderen Wissenschaften unmittelbar treffen, da sie die zugrunde liegenden Parameter für ihre Modelle besser einschätzen können.
Nicholas Mancuso
Erwähnenswert ist, was ich in dem unwahrscheinlichen Szenario mit P = NP als wahrscheinlichste Alternative erwarten würde: Es wird nämlich der Beweis erbracht, dass kein Problem in NP nicht in P sein kann, sondern ohne einen beispielhaften P-Algorithmus für einen NP- vollständiges Problem. Nur weil jemand nachweisen kann, dass es in P eine Lösung geben muss, heißt das nicht, dass wir diese Lösung tatsächlich finden oder ihre Richtigkeit überprüfen können. Ironischerweise könnte dieser letzte Teil einfacher sein, wenn ein P-Algorithmus für ein NPC-Problem existiert, aber nun, das ist ein bisschen ein
Henne
5
Das "konstruktive" Stück ist ein roter Hering. Es gibt ein bekanntes spezifisches Programm, das SAT in der Polynomzeit löst, wenn (im Wesentlichen ist es auf allen SAT-Solvern gleich Null). Somit stellt ein klassischer Beweis von P = N P bereits sicher, dass sich dieser spezielle SAT-Löser in P befindet , sodass wir auch einen konstruktiven Beweis erhalten. P=NPP=NPP
Andrej Bauer

Antworten:

34

Die Leute haben gute Antworten gegeben, wenn man annimmt, dass mit einer wirklich großen Konstante ist. Ich werde den Optimisten spielen und davon ausgehen, dass wir einen Beweis für P = N P mit einer sehr kleinen Konstante finden. Vielleicht nicht wahrscheinlich, aber ich werde versuchen, einen Einblick zu geben, was passieren würde, wenn wir alle N P- Probleme effizient lösen könnten .P=NPP=NPNP

  • Compiler: Einige Computerprogramme würden etwas schneller werden, da Compiler für die Registerzuweisung die Grafikfarbe verwenden. Wir wären in der Lage, eine große Anzahl von Registern genau zuzuordnen. Bestehende Compiler, die eine ungefähre Lösung (wie Akkorddiagramme) verwenden, würden eine bessere Ausgabe erhalten, und diejenigen, die eine genaue Lösung verwenden, würden eine schnellere Ausgabe erhalten.

  • Standort der Einrichtung: Unternehmen könnten den optimalen Ort für die Platzierung von Fabriken und Lieferdepots für den Versand an ihre Filialen finden, wenn möglicherweise Tausende von Filialen und Fabriken vorhanden sind. Wäre wahrscheinlich keine enorme Verbesserung gegenüber modernen Annäherungen, würde aber die Kosten senken.

  • Flugtickets kaufen: Flugtickets sind seltsam, da sie nicht der Dreiecksgleichheit folgen. Manchmal ist es billiger, von A -> B -> C zu fliegen als direkt von A -> C, was beim Modellieren von Entfernungen nicht auffällt. Es wäre einfach, eine Website zu erstellen, die die absolut günstigste Abfolge von Flügen findet, die eine Reihe von Städten besuchen und in Ihrer Heimatstadt beginnen und enden.

  • Schaltungsdesign: Elektrische Schaltungen auf einem Chip sind im Grunde boolesche Formeln. Dinge wie die Minimierung könnten effizient berechnet werden, damit unsere Hardware ein bisschen effizienter wird.

  • P=NP

NP

jmite
quelle
5
Zitat aus Wikipedia zu P vs NP : If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found.Mir ist bewusst, dass sich dies möglicherweise nicht auf die praktischen Anwendungen bezieht, aber es sieht definitiv wie eine Übertreibung aus, wenn ich es mit Ihrer Antwort vergleiche. Worüber redet er wirklich?
Nik Kyriakides
4
@Nicholas Etwas übertrieben, aber ich kann den Punkt sehen. Unglaublich ungenau zu sein: Probleme NPbedeuten, dass wir überprüfen können, ob eine Lösung in Polynomzeit korrekt ist, aber ein Problem Pbedeutet, dass wir eine Lösung in Polynomzeit finden können. Wenn NP=Pdies bedeutet, ist es der gleiche Aufwand, zu überprüfen, ob eine Lösung korrekt ist oder eine Lösung zu finden. Konstante Faktoren, die in der Realität offensichtlich einen großen Unterschied machen, werden dabei völlig ignoriert.
Voo
2
Können Sie die Auswirkungen auf kryptografische Anwendungen erwähnen?
ζ--
5
Wenn P = NP, dann wären Primfaktoren in Polynomzeit berechenbar (es ist bekannt, dass die Primfaktorisierung in Polynomzeit verifizierbar ist). Viele kryptografische Algorithmen - wie der unglaublich verbreitete RSA - basieren auf der Schwierigkeit, primäre Faktorisierungen zu berechnen. Wenn die oben genannte "Konstante" klein genug ist, können alle RSA-Verschlüsselungen, unabhängig von der Schlüsselgröße, sofort wertlos gemacht werden.
user2407038
3
n100n99n2nlogn
30

n2100nn100

Was passiert hier? Es gibt verschiedene Probleme mit der Frage P vs. NP:

  1. Es geht nur um den schlimmsten Fall.
  2. Es ist nur asymptotisch.
  3. Alle Polynomzeitgrenzen sind gleich.

Diese Probleme werfen Zweifel an der Relevanz für die reale Welt auf. Jetzt könnte es passieren, dass für 3SAT ein sehr schneller Algorithmus gefunden wird, der sogar symmetrische Verschlüsselungen aufhebt. Ich halte dies jedoch für sehr unwahrscheinlich. Andererseits ist es vollkommen konsistent, dass P sich von NP unterscheidet, während berücksichtigt wird, dass es praktisch ist; Dies würde bestimmte Verschlüsselungsverfahren mit öffentlichen Schlüsseln unterbrechen. Dies ist eine wahrscheinliche Situation, die Auswirkungen hätte, aber nichts mit der Frage von P gegen NP zu tun hat.

Die P vs. NP-Frage mag aus mathematischer Sicht natürlich sein, aber ihre praktische Relevanz ist aus meiner Sicht zweifelhaft. Andererseits könnte die Forschung zu dieser Frage praktische Auswirkungen haben oder auch nicht. es wird nicht von diesem Aspekt geleitet.

Yuval Filmus
quelle
2
Ein Beweis könnte keinen P-Algorithmus für ein NPC-Problem beinhalten, aber wenn es die praktische Konsequenz wäre, wäre es plötzlich lohnenswert, nach den spezifischen NP-Problemen (oder besser gesagt, jetzt P-Problemen) zu suchen, die in großem Maßstab von Wert sind und auch nachvollziehbare Konstanten. Momentan bedeutet NP-komplett zu sein, dass es wahrscheinlich nicht die Mühe wert ist, überhaupt hinzuschauen. Die praktische Konsequenz in der Praxis würde also davon abhängen, wie NP als P dargestellt wird - Sie würden auf einen Beweis hoffen, der die Konstruktion eines P-Algorithmus für ein NPC-Problem ermöglicht, und alles hängt von den Details dieses Algorithmus ab.
Eamon Nerbonne
Wenn Sie 2 ^ 100n für 3SAT gelöst haben, werde ich das gerne ASIC-Board und drohen, RSA-2048 in gerade genug Zeit zu knacken, um 30-jährige Root-Zertifikate zu einer schlechten Idee zu machen.
Joshua
11

Auch ohne P = NP sind die heutigen Computer unglaublich leistungsfähig.


Edit 22 Jan 2018 Ich habe jetzt herausgefunden, wie ich den im folgenden Beispiel zitierten Text "interpretieren" sollte. Es war meine eigene Schuld, das inverse Element musste eindeutig sein . Hier ist meine Eingabedatei vom 22. Dezember 2014 ( addinvrig.in ) und hier ist die feste Eingabedatei vom heutigen Tag ( addinvrigFixed.in ). Das Entscheidende ist: (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).Die Leistungsfähigkeit der automatischen Argumentationswerkzeuge selbst fasziniert mich immer noch, auch wenn sie mich nicht davor bewahren können, die Schriften anderer Menschen falsch zu interpretieren.

Die Verwendung automatisierter Argumentationstools ist für mich überraschend nützlich, wenn ich auf zitierte Theoreme stoße, bei denen ich nicht sicher bin, wie ich den Text "interpretieren" soll :



x,yS(xy)=xy=xyxy=xy
aaSSaaSS

Ich habe meine prover9-Eingabedateien für diesen Satz angepasst und wurde sofort als Gegenbeispiel für den Satz gezeigt. Ein geringfügiges Modifizieren der Annahmen führte zu vielen ähnlichen wahren Theoremen, was es höchstwahrscheinlich macht, dass Karvellas tatsächlich einen korrekten Theorem aufstellte und bewies, der hier nur falsch zitiert wurde. Googeln nach dem Hinweis auf diesen Satz brachte nur eine weitere Veröffentlichung hervor, in der Karvellas noch ungenauer zitiert wurde .


Dies ist eine unglaublich unvollständige Sammlung computerunterstützter Ergebnisse für spezifische Probleme, die im Allgemeinen nicht zu lösen sind, wenn P! = NP. Vielleicht macht diese Sammlung zumindest einigen Lesern klar, dass wir alle dazu neigen, die Leistungsfähigkeit von Computern in diesem Bereich zu unterschätzen. Viele andere Antworten auf diese Frage scheinen darauf hinzudeuten, dass es keine großen Konsequenzen geben würde, wenn Computer (geringfügig) besser in der Lage wären, hartnäckige Probleme zu lösen. Aber Computer sind immer besser in der Lage, unlösbare Probleme zu lösen (da viel Zeit und Geld aufgewendet wird, um dies zu erreichen), und dies hat sehr reale Konsequenzen. Wenn P = NP bewiesen würde, würde vielleicht das Bewusstsein dafür, was Computer tatsächlich können (auch heute noch), steigen und mehr Menschen würden Computer verwenden, um ihnen bei solchen Aufgaben zu helfen. (PS: Ich bin überzeugt, dass P! = NP,

Thomas Klimpel
quelle
7

Es gibt viele Meinungen zu den realen Auswirkungen von P = NP. Wie aus anderen guten Antworten hervorgeht, gibt es hauptsächlich zwei Denkschulen. Einer ist, dass ein P-Zeit-Algorithmus aufgrund von "unerwarteten Anomalien", die mit der Abstraktion verbunden sind, möglicherweise sehr schwierig oder nicht realisierbar ist. z.B:

  • Das Programm ist möglicherweise zu "groß", um tatsächlich Code zu schreiben
  • Es könnte sich um eine sehr große Konstante handeln, sodass sie für alle Instanzen, die sich in Reichweite der "terrestrischen Berechnung" befinden, noch lange andauert, dh die Effizienz greift nur bei sehr großen Instanzen. Es ist bekannt, dass einige Algorithmen tatsächlich in diesen Fall passen, wie kürzlich von Knuth ausgeführt (Frage 15).

Im Allgemeinen bin ich auf der Suche nach mehr Fokus auf Algorithmen, die in Bezug auf Probleme, deren Größe n machbar ist, schnell funktionieren. Der größte Teil der heutigen Literatur befasst sich mit asymptotisch großen Algorithmen, die jedoch nur dann hilfreich sind, wenn n die Größe des Universums überschreitet.

Eine berühmte Fallstudie stammt von Impagliazzo, wie in einer anderen Antwort von J. zitiert. Sein Aufsatz wurde jedoch in der Zwischenzeit etwas extrapoliert. Hier ist eine großartige neue Referenz von einem Experten, der sich in einer Art Science-Fiction-Zukunftsszenario mit dieser Frage befasst, ch2 / p11. zusammenfassend

Das goldene Ticket: P, NP und die Suche nach dem Unmöglichen von Lance Fortnow

  • "Wenn sich herausstellt, dass P = NP und wir effiziente Algorithmen für alle NP - Probleme haben, wird sich die Welt auf eine Weise verändern, die das Internet wie eine Fußnote in der Geschichte erscheinen lässt. Es wäre nicht nur unmöglich, alle diese Änderungen zu beschreiben, sondern auch die Die größten Auswirkungen der neuen Technologien wären unmöglich vorherzusagen. "

  • Algorithmus schnell auf Supercomputer implementiert. Boeing beauftragt umgehend mit der Entwicklung eines besseren Tragflächendesigns für ein neues Flugzeug, mit dem es nonstop von London nach Sydney fliegen kann.

  • Suchalgorithmus, der verwendet wird, um einen neuen Algorithmus zu finden, der noch schneller ist und die ursprüngliche P = NP-Lösung optimiert. Endet mit dem Ergebnis von 42 Millionen Zeilen unverständlichem Code. Nannte den "Urbana-Algorithmus"

  • Algorithmus, der verwendet wird, um maßgeschneiderte Krebsbehandlungen / Nahkuren zu finden, die auf Einzelpersonen zugeschnitten sind. heilt Krebs, AIDS, Diabetes, aber die Erkältung bleibt ein Rätsel

  • Mit dem Super-Scheduling-Algorithmus können Prognostiker "unglaubliche Fortschritte bei der Wettervorhersage erzielen und Temperatur, Wind, Wolkendecke und Niederschlag fast ein Jahr im Voraus genau vorhersagen. Ähnliche Algorithmen retten jetzt Leben, indem sie Stürme, Tornados und Hurrikane genau vorhersagen, damit die Menschen dies können nach Bedarf vorbereiten oder evakuieren. "

  • Hochgenaue Gesichtserkennung

  • Der Computer kann 3D-Modelle einer Szene in Echtzeit aus verschiedenen Kamerawinkeln rekonstruieren

  • Computeralgorithmen steuern den Kamerabetrieb für Sportereignisse (anstatt von Menschen gesteuert)

  • Automatisierte Kommentare und Wiederholungen werden vom Algorithmus generiert, einschließlich ausgewählter Blickwinkel und Statistiken, und in Echtzeit in jeder Sprache erstellt

  • Fantasy-Baseball / Sport nehmen mit hochpräzisen Simulationen eine neue Dimension an

  • Der Geschmack der Speisen wird durch den Algorithmus verbessert

  • Der Algorithmus könnte verwendet werden, um "so ziemlich alles zu lernen, einschließlich was gute Kunst, populäre Musik und Wörter ausmacht, die die Seele bewegen. Denken Sie daran, dass P = NP bedeutet, was wir testen können, was wir finden können. Wenn Sie also einen Algorithmus haben." Um Größe zu erkennen, können Sie den Algorithmus erneut verwenden, um diese Größe schnell zu finden. "

  • Der Politiker verwendet einen Computeralgorithmus, um großartige Reden zu erkennen und eine zu generieren, die den Mustern entspricht. Die Sprache im Internet wird viral.

  • Menschen erzeugen komplette Kunstwerke aus unvollständigen / unvollendeten Kunstwerken, zB Symphonien. Sie verwenden Algorithmen, um neue Beatles / Elvis-Datensätze zu generieren. Neue Kunst, Romane, Theaterstücke und Gedichte, zB romantische Komödie mit Humphrey Bogart / Julia Roberts.

  • Amazon kann auf Anfrage maßgeschneiderte Romane für Einzelpersonen erstellen. NBC erstellt Live-Action-Adventure-Fernsehserien, die vollständig vom Computer erstellt wurden

  • Simulierte virtuelle Realität in Videospielen, die beliebige Aktionen der Spieler anstelle eines festgelegten Satzes möglicher Handlungsstränge zulässt.

  • Strafverfolgungsbehörden verwenden Algorithmen als "unglaubliches Instrument zur Aufklärung von Verbrechen, das anscheinend das Unmögliche tut, um Verdächtige aufzuspüren". Computeralgorithmus kann wahrscheinliche Gesichter (für zusammengesetzte Skizzen) nur mit DNA rekonstruieren. Die Polizei ermittelt einen Mordverdächtigen anhand einer umfangreichen Suche in der Datenbank mit Führerscheinfotos, die an der generierten Skizze (aus DNA) ausgerichtet ist.

Leider wird nicht viel, was Fortnow oben skizziert, von aktueller wissenschaftlicher Literatur gestützt, außer vielleicht einer einfallsreichen Extrapolation von Impagliazzos-Welten. es würde viel mehr erfordern, um diesen Punkt für Punkt zu analysieren, aber zusammenfassend scheint alles unterhaltsames, aber fantastisches / Wunschdenken zu sein (oder vielleicht ist das sein verschleierter Punkt). Tatsächlich gibt es wissenschaftliche Prinzipien, die mit vielen der Punkte in Konflikt stehen. Und beachten Sie, dass Fortnow ein Sportfan ist und in diesem Bereich eine erweiterte Metapher entwickelt. Könnte dies eher ein Hinweis darauf sein, dass Menschen in Rillen denken ?

Zum Beispiel ist bekannt, dass der "Schmetterlingseffekt" darauf hindeutet, dass eine genaue Wettervorhersage über einen (etwa) Mehrtageshorizont hinaus aufgrund der "empfindlichen Abhängigkeit von den Anfangsbedingungen" unmöglich ist (und Fortnow hat später in seinem Blog zugestanden, genau dies wiederholt zu kritisieren Punkt). Es gibt auch viele Beweise dafür, dass Computer bei hochmenschlich-subjektiven Aufgaben, wie dem Erzeugen oder Identifizieren einflussreicher Kunst, versagen (eine Aufgabe, die selbst erfahrene Menschen nicht konsequent lösen können).

Tatsächlich geht die ganze Frage von einer kontrafaktischen oder falschen Voraussetzung aus . Beachten Sie, dass eine große Mehrheit der befragten Experten denkt / glaubt, trotz des Mangels an bislang unbestreitbaren Beweisen, P ≠ NP. und es ist natürlich, es mit anderen bekannten Gesetzen / Beschränkungen / Beschränkungen wie der Thermodynamik (z. B. Unmöglichkeit der ständigen Bewegung / freien Energie ) und Statistiken zu vergleichen, z. B. dem Satz "kein freies Mittagessen" .

Das Fazit ist also, dass vielleicht sogar erfahrene Wissenschaftler das Ergebnis von P = NP nicht genau vorhersagen können. Die vielleicht beste Antwort für den Moment ist zuzugeben, dass die Menschen derzeit keine gute Antwort haben.

vzn
quelle
1
Anmerkung: Die beiden Denkrichtungen lauten "P = NP ist möglicherweise keine große Sache" bis "es wäre eine große Sache", wobei Fortnow die letztere Position vertritt. Tatsächlich sind diese beiden Denkrichtungen jedoch nicht für die gängige CS-Hypothese / Vermutung geeignet. mit anderen Worten (wie Aaronson hingewiesen hat seine nicht) die Art von Frage , die beispielsweise angesprochen werden können nur als Team A und Team B. das Übergewicht des wissenschaftlichen Beweises scheint P ≠ NP ... anzuzeigen
VZN
1
+1 für das Fortnow-Buch. Ich würde es selbst vorschlagen. Eine kürzere Liste der (großartigen) Implikationen von P = NP ist in cacm.acm.org/magazines/2009/9/… (ebenfalls von Fortnow) enthalten.
Fizz
7

P gegen NP, technisch gegen moralisch

O(n2)O(nlgn)265536+21024n256O(nlgn)

Was passiert also, wenn P = NP moralisch wahr ist?

QQRichtig, dann können all diese Probleme sehr schnell gelöst werden. Um nur ein Beispiel zu nennen, Sie können die besten Gewichte für sehr komplizierte Modelle des maschinellen Lernens lernen. Sie können Verschlüsselungsprotokolle unterbrechen.

Wenn Sie wissen, dass Sie ein NP-vollständiges Problem nicht bei allgemeinen Eingaben, sondern bei Eingaben mit bestimmten Eigenschaften lösen möchten, müssen Sie sich nicht um das allgemeine Problem kümmern. Sie müssen nur das einfachere Problem lösen. Leider ist es oft nicht einfach festzustellen, welche Art von Eingaben Sie in der Praxis interessieren.

Kaveh
quelle
3

Welche nahezu unmittelbare Auswirkung hätte ein gründlicher, genauer Nachweis von P = NP mit einer bereitgestellten Lösung auf die Praxis?

Es würde wahrscheinlich eine Menge großartiger Dinge daraus werden, aber das würde niemanden interessieren.

Das Problem ist , dass die Grundlage für (fast) all moderne Verschlüsselung auf der Annahme , dass P basiert nicht gleich NP. Die Verschlüsselung, die Ihr Kennwort schützt, während es über das Internet übertragen und in Datenbanken gespeichert wird. Die Verschlüsselung, die Kreditkartendaten schützt , während diese über das Internet übertragen werden ... Die Verschlüsselung, die Milliarden von täglichen Finanztransaktionen schützt, die unsere globale Wirtschaft in den riesigen Organismus einbinden, der sie ist.

Im besten Fall bedeutet P = NP, dass aufhört. Die Leute verwenden wieder Bargeld, und Banken versuchen, diese Bargeldabhebungen auf einem nicht verbundenen Medium aufzuzeichnen, da Transaktionen an eine Zentrale nicht mehr vertrauenswürdig sind. Dies dauert möglicherweise einige Monate, bis eine bessere Verschlüsselung weltweit implementiert ist. I'm besten fall.

Im schlimmsten Fall bedeutet P = NP, dass jemand die Welt zerstört. Die Währung baut auf dem Konzept des Vertrauens auf. Sie schätzen einen Dollar, weil Sie darauf vertrauen, dass Ihr Nachbar Ihnen Waren oder Dienstleistungen im Wert von einem Dollar dafür gibt. Sie schätzen Ihren Computer und sagen, dass Sie 500 Dollar auf der Bank haben, weil Sie Ihre Karte klauen und Waren und Dienstleistungen im Wert von 500 Dollar erhalten können ...

Was wäre, wenn du dem nicht trauen könntest ? Wenn P = NP, könnte sich jemand als verschiedene Banken, Regierungen und Personen ausgeben und den Währungsbetrag auf jedem Konto effektiv zufällig bestimmen. Löschen Sie die Währung in jedem Konto. Sicher, verschiedene Banken haben Backups, aber wie lange ist ihre Verschlüsselung aufgebrochen? Welche Transaktionen waren gut und welche waren falsch? Es ist unmöglich zu wissen.

Sobald dieses Vertrauen gebrochen ist, entsteht Chaos. Alle Vorteile, die sich beispielsweise aus der Bewältigung des Problems des Handlungsreisenden ergeben, werden ignoriert, da die Menschen Schwierigkeiten haben, sich selbst zu ernähren.

Die Realität liegt wahrscheinlich irgendwo dazwischen, aber hoffentlich zeichnet dies ein ausreichend großes Bild davon, wie wichtig dieses Problem ist.

Telastyn
quelle
4
Crypto wäre nicht so kaputt, wie Sie vermuten. Selbst wenn P = NP ist, können Sie zufällig erzeugte Bits (z. B. Schlüssel) nicht deterministisch vorhersagen. Aus diesem Grund funktioniert das One Time Pad immer. Die Annahmen zur rechnerischen Härte helfen nur, die Verwendung kürzerer Schlüssel und asymmetrischer Schemata zu rechtfertigen.
Mdxn
2
@mdx - es ist schon eine Weile her, dass ich mich eingehend damit beschäftigt habe, aber spielt es keine Rolle, ob Sie die Schlüssel vorhersagen können, wenn Sie die Schlüssel schnell und einfach entschlüsseln können?
Telastyn
Bei der Verschlüsselung mit privaten Schlüsseln versuchen wir im Idealfall, die Zufälligkeit von über die Nachricht auf eine Weise zu verteilen, die nur schwer rückgängig zu machen ist. Dies hat den Vorteil, dass wir kürzere Schlüssel verwenden können, zeit- und platzsparend sind und dennoch eine gute Sicherheit erzielen. Wenn ein Angreifer dies praktisch rückgängig machen kann, geschieht dies nicht. Wenn P = NP, dann müssten wir die Sicherheit auf schwierigere Probleme stützen. Der Nachteil ist, dass das Ver- und Entschlüsseln auch rechenintensiver ist.
Mdxn
Während ein privates Schlüsselschema die informationstheoretische Sicherheit vor der Zufälligkeit des Schlüssels bewahren kann, wird dies bei einem öffentlichen Schlüsselsystem nicht der Fall sein. In dieser Situation könnten Sie den Schlüssel herausziehen. Wiederum können wir in der Welt, in der P = NP ist, ein schwierigeres Problem verwenden, um die Sicherheit davon abhängig zu machen, ob wir eines haben. Es wäre ebenfalls weniger effizient.
Mdxn
1
@mdx: Einmal-Pads sind keine praktikable Lösung für die Anforderungen des Internetverkehrs, da das Pad sicher an den Empfänger geliefert werden muss, bevor es verwendet werden kann. Jetzt haben Sie das Problem nur um einen Schritt zurückgedrängt.
Mason Wheeler
2

Der Aufwand für Geräte, Strom und Cloud-Ansätze wird massiv sinken. Viele Dinge werden gerade mit brachialer Gewalt berechnet, oder Näherungen, die immer noch einiges an brutaler Gewalt erfordern. Wir werden nicht mehr alle diese massiv paralisierten Brute-Force-Berechnungen durchführen.

Dies ist keineswegs die einzige Verwendung von Cloud-Computing, wird sich aber dennoch spürbar auf den Energieverbrauch, die Cloud-Verarbeitung usw. auswirken. Allein die Energieeinsparungen könnten sich auf unseren CO2-Fußabdruck auswirken.

Die KI wird auch viel besser. Wir könnten endlich einen Computer haben, der die besten GO-Spieler sein kann, und Ihr Grafikrechner wird Sie beim Schach schlagen.

dsollen
quelle
4
n×n19×19n×n
Sie gehen davon aus, dass die Probleme, die wir derzeit durch Brute-Forcing lösen, in NP sinken und alle von ihnen sofort verwundet werden können. Das ist alles andere als wahr.
Yves Daoust
0

Und die Vermutung, die widerlegt wird, bedeutet nicht, dass alle Probleme von praktischem Nutzen mit einem Fingerschnipp gelöst würden. Erstens können sie immer noch härter sein als NP.

Yves Daoust
quelle
-1 weil Ihr Argument nicht von Details des Systems abhängt, über das es argumentieren soll. Durch dasselbe Argument haben wir gelernt, in einer Welt ohne Autos zu leben, also würde ich nicht erwarten, dass Autos eine Revolution auslösen würden. Umgekehrt haben wir gelernt, in einer Welt ohne MP3-Schuhe zu leben, und ich würde nicht erwarten, dass sie eine Revolution auslösen. Eines dieser Beispiele ist eindeutig falsch, das andere wahrscheinlich wahr. Ihre Schlussfolgerung zu P vs NP könnte entweder sein.
David Richerby
@DavidRicherby: danke für die Erklärung der Ablehnung.
Yves Daoust