Quel serait l'impact de P = NP? [fermé]

Je me prépare pour un test et je ne trouve pas de réponse claire à la question: quel serait l'impact de prouver que PTIME = NPTIME. J'ai vérifié wikipedia et il vient de mentionner que cela aurait "un impact profond sur les mathématiques, l'IA, les algorithmes .." etc.

N'importe qui peut me donner une réponse?

La première chose qui me vient à l'esprit est que la sécurité de la cryptographie à clé publique dépend actuellement de l'impossibilité de forcer les problèmes mathématiques de force brute qui sont dans la classe de difficulté NP. Si P = NP, tout ce qui dépend de PKC (y compris HTTPS, ce qui signifie que toute l'infrastructure de commerce électronique moderne et mondiale ) devrait être retravaillé!

Ceci est couvert dans L'état du problème P par rapport à NP . Vaut vraiment le détour.

Quelques points saillants de l'article (cités dans la section What If P = NP? ):

• La cryptographie à clé publique devient impossible.
• Puisque tous les problèmes d'optimisation NP-complets deviennent faciles, tout sera beaucoup plus efficace. Le transport de tous les formulaires sera planifié de manière optimale pour déplacer les personnes et les marchandises plus rapidement et moins cher. Les fabricants peuvent améliorer leur production pour augmenter la vitesse et créer moins de déchets.
• L'apprentissage devient facile en utilisant le principe du rasoir d'Occam - nous trouvons simplement le plus petit programme cohérent avec les données. La reconnaissance de la vision presque parfaite, la compréhension et la traduction du langage et toutes les autres tâches d'apprentissage deviennent triviales. Nous aurons également de bien meilleures prévisions du temps et des tremblements de terre et d'autres phénomènes naturels.
• P = NP aurait également de grandes implications en mathématiques. On pourrait trouver des preuves courtes et entièrement logiques pour les théorèmes, mais ces preuves sont généralement extrêmement longues. Mais nous pouvons utiliser le principe du rasoir Occam pour reconnaître et vérifier les preuves mathématiques telles qu'elles sont généralement écrites dans les revues. On peut alors trouver des preuves de théorèmes qui ont des preuves de longueur raisonnable disons en moins de 100 pages. Une personne qui prouve P = NP rentrerait à pied de l'Institut Clay non pas avec un chèque de 1 million de dollars mais avec sept (en fait six depuis que la conjecture de Poincaré semble résolue).

La plupart des problèmes NP complets ont des applications réelles "intéressantes". P=NPaura beaucoup de conséquences:

• Il sera possible de résoudre exactement les problèmes d'optimisation qui sont actuellement approximés. C'est le cas du problème du voyageur de commerce et du problème de planification des travaux
• Il casse certaines mesures de sécurité basées sur le fait que le temps de calcul requis est énorme. Par exemple, de nombreux schémas et algorithmes de cryptage en cryptographie sont basés sur la factorisation des nombres, l'algorithme le plus connu ayant une complexité exponentielle. Ces algorithmes deviendront inutiles si un algorithme polynomial est trouvé.

L'essentiel, c'est la nature des problèmes connus pour être NP-complets. Ce ne sont pas seulement des problèmes créés par quelques scientifiques éloignés pour se divertir les uns les autres. Ils peuvent être exprimés en termes commerciaux. En fait, certains intervieweurs d'emploi aiment cacher les problèmes NP-complets dans leurs questions afin de tester les candidats.

Ces possibilités sont couvertes dans les cinq mondes d'Impagliazzo .

Voici quelques points à retenir:

• L'intelligence artificielle pourrait faire un bond de géant. Par exemple, avec suffisamment de «données d'apprentissage», les circuits les plus courts pour produire les sorties correctes à partir des entrées représenteraient la meilleure méthode de traduction. En particulier, il deviendrait trivial d'avoir une parfaite reconnaissance vocale et une parfaite traduction linguistique. Prenant cette idée plus loin, si vos données d'entraînement sont des films primés aux Oscars, cela peut générer plus de films primés aux Oscars pour vous.

• Les algorithmes enseignés dans les écoles seraient radicalement différents. Au lieu d'apprendre autant de techniques algorithmiques différentes , les cours se concentreraient sur la réduction des problèmes à la vérification des bonnes réponses. Cela simplifierait considérablement la programmation.

• L'économie deviendrait beaucoup plus efficace. Il y aurait des perturbations, y compris le déplacement des programmeurs. La pratique de la programmation elle-même consisterait davantage à recueillir des données de formation qu'à rédiger du code. Google aurait les ressources pour exceller dans un tel monde.

• Parce que la cryptographie à clé publique serait «hors service», Amazon devrait vous envoyer un tampon unique sur une clé USB pour effectuer des transactions sécurisées.

• Des preuves mathématiques pourraient être générées et vérifiées automatiquement.

Globalement, cela introduirait une singularité technologique; les implications de P = NP seraient d'une grande portée. En outre, Lance Fortnow aborde ce point dans un article de blog distinct que vous devez lire.

L'impact de la preuve de P = NP inclurait un regain d'intérêt pour la recherche d'un algorithme de réduction. Les gens essaieraient également de trouver des bornes inférieures sur les constantes associées à l'algorithme de réduction.

Prouver P = NP ne serait pas aussi significatif que le prétendent d'autres réponses, car il pourrait prendre la forme d'une preuve de connaissance nulle. Connaître P = NP sans connaître l'algorithme de réduction serait peu différent de la situation actuelle.

Imaginez que quelqu'un prouve que l'algorithme de réduction existe mais qu'il est O (sqrt (n) + 2 ^ 4096).