Qu'est-ce que la conjecture P≠NP ? Explication claire d'un problème non résolu en théorie de la complexité et la différence entre les classes P et NP

Concernant le plus grand problème non résolu de l'informatique 'La conjecture P≠NP', explique clairement la vue d'ensemble du point de vue des machines de Turing déterministes, tout en abordant la différence entre la 'Classe P', qui peut être résolue en temps polynomial, et la 'Classe NP', où la validité de la solution peut être vérifiée en temps polynomial.

Aperçu

1
La classe P est la classe des problèmes qui peuvent être décidés en temps polynomial par une machine de Turing déterministe, et la classe NP est la classe des problèmes pour lesquels, étant donné une preuve (appelée Témoin ou Witness) que la réponse est Oui, la validité du Témoin peut être jugée (cela s'appelle la vérification) en temps polynomial. Étant donné que les problèmes décidables en temps polynomial peuvent être vérifiés en temps polynomial, il est évident que P⊆NP, mais il n'est pas clair si P est un sous-ensemble propre de NP. Il n'y a pas encore de preuve, mais de nombreux chercheurs pensent que P≠NP. La conjecture selon laquelle la classe P et la classe NP ne sont pas égales est appelée la "Conjecture P≠NP".

Site de référence : https://daigakudenki.com/np-hard/