Quale sarebbe l'impatto di P = NP? [chiuso]

La prima cosa che viene in mente è che la sicurezza della crittografia a chiave pubblica attualmente dipende dall'essere incapace di risolvere problemi di matematica a forza bruta nella classe di difficoltà NP. Se P = NP, tutto ciò che dipende da PKC (incluso HTTPS, che significa l'intera infrastruttura di ecommerce moderna e mondiale ) dovrebbe essere rielaborato!

Questo è trattato in The Stato del problema P Versus NP . Sicuramente vale la pena leggere.

Alcuni punti salienti dell'articolo (citato da What If P = NP? section ):

• La crittografia a chiave pubblica diventa impossibile.
• Poiché tutti i problemi di ottimizzazione completi di NP diventano facili, tutto sarà molto più efficiente. Il trasporto di tutte le forme sarà programmato in modo ottimale per spostare persone e merci in modo più rapido ed economico. I produttori possono migliorare la loro produzione per aumentare la velocità e creare meno sprechi.
• L'apprendimento diventa facile utilizzando il principio del rasoio di Occam: troviamo semplicemente il programma più piccolo coerente con i dati. Il quasi perfetto riconoscimento visivo, la comprensione e la traduzione della lingua e tutti gli altri compiti di apprendimento diventano banali. Avremo anche previsioni molto migliori di tempo, terremoti e altri fenomeni naturali.
• P = NP avrebbe anche grandi implicazioni in matematica. Si potrebbero trovare prove brevi e pienamente logiche per i teoremi, ma queste prove sono di solito estremamente lunghe. Ma possiamo usare il principio del rasoio Occam per riconoscere e verificare prove matematiche come tipicamente scritte in riviste specializzate. Possiamo quindi trovare le dimostrazioni di teoremi che contengono prove di durata ragionevole in meno di 100 pagine. Una persona che dimostri P = NP andrebbe a casa dall'Istituto di Clay non con un assegno da $ 1 milione ma con sette (in realtà sei da quando la Congettura di Poincaré appare risolta).

La maggior parte dei problemi completi di NP ha applicazioni di vita reale "interessanti". P=NP avrà molte conseguenze:

• Sarà possibile risolvere esattamente problemi di ottimizzazione attualmente approssimati. Questo è il caso del problema del venditore ambulante e del problema di pianificazione del lavoro
• Rompe alcune misure di sicurezza che si basano sul fatto che il tempo di calcolo richiesto è enorme. Ad esempio, molti schemi di crittografia e algoritmi in crittografia si basano sulla fattorizzazione del numero, l'algoritmo più noto con complessità esponenziale. Questi algoritmi diventeranno inutili se viene trovato un algoritmo polinomiale.

La linea di fondo è sulla natura dei problemi noti per essere NP-completo. Questi non sono solo problemi creati da pochi scienziati in una posizione remota per intrattenere l'un l'altro. Possono essere espressi in termini commerciali. In effetti, ad alcuni intervistatori di lavoro piace nascondere i problemi NP-completi nelle loro domande per testare i candidati.

Queste possibilità sono trattate in I cinque mondi di Impagliazzo .

Ecco alcuni punti da asporto:

• L'Intelligenza Artificiale sarebbe in grado di fare un salto da gigante. Ad esempio, con abbastanza "dati di addestramento", i circuiti più brevi per produrre gli output corretti dagli ingressi rappresenterebbero il miglior metodo di traduzione. In particolare, sarebbe banale avere un perfetto riconoscimento vocale e traduzione linguistica. Prendendo ulteriormente questa idea, se i tuoi dati di allenamento sono film vincitori di Oscar, puoi generare altri film vincitori di Oscar per te.

• Gli algoritmi insegnati nelle scuole sarebbero radicalmente diversi. Invece di imparare così molte diverse tecniche algoritmiche , i corsi si concentrerebbero sulla riduzione dei problemi per la verifica delle risposte corrette. Ciò semplificherebbe notevolmente la programmazione.

• L'economia diventerebbe molto più efficiente. Ci sarebbero interruzioni, tra cui forse la sostituzione dei programmatori. La pratica della programmazione stessa sarebbe più concentrata sulla raccolta di dati di addestramento e meno sulla scrittura del codice. Google avrebbe le risorse per eccellere in un mondo del genere.

• Poiché la crittografia a chiave pubblica sarebbe "fuori", Amazon avrebbe bisogno di inviarti un one-time-pad su una pen drive per fare transazioni sicure.

• Le prove matematiche possono essere generate e verificate automaticamente.

Nel complesso, introdurrebbe una singolarità tecnologica; le implicazioni di P = NP sarebbero di vasta portata. Inoltre, Lance Fortnow affronta questo punto in un blog post separato che dovresti leggere .

L'impatto di dimostrare P = NP includerebbe un rinnovato interesse nel trovare un algoritmo di riduzione. Le persone proverebbero anche a trovare dei limiti inferiori sulle costanti associate all'algoritmo di riduzione.

Dimostrare che P = NP non sarebbe significativo come affermano altre risposte, perché potrebbe presentarsi sotto forma di una prova a conoscenza zero. Conoscere P = NP senza conoscere l'algoritmo di riduzione sarebbe poco diverso dalla situazione attuale.

Immagina se qualcuno dimostrasse che l'algoritmo di riduzione esiste ma è O (sqrt (n) + 2 ^ 4096).