Comment les premiers problèmes NP-complets ont-ils été démontrés?

Question

De l'entrée wikipedia sur NP-Complete:

"Le moyen le plus simple de prouver qu'un nouveau problème est NP-complet est tout d'abord de prouver qu'il se trouve dans NP, puis de le réduire à un problème connu de NP-complet"

Je suis à peu près sûr de comprendre ceci: si j'ai un problème, je peux montrer qu'il est NP-complet si je:

1. montre qu'il est en NP (une solution à le problème peut être vérifié dans temps polynomial sur un machine de Turing non déterministe)

2. Montrer qu'un problème connu comme NP-Complete peut être résolu "réduit" au nouveau problème

Ma question est donc la suivante: comment les premiers problèmes NP-complets ont-ils été «prouvés» comme étant NP-complets? À un moment donné, l'ensemble des problèmes connus de NP-complet devait être nul, ce qui aurait rendu impossible le recours à l'étape 2 du processus ci-dessus.

Cela me fait penser qu'il existe une méthode de preuve différente que je ne connais pas. Soit cela, soit peut-être la totalité de la propriété NP-complete est "supposée" pour certains problèmes en raison de l'absence d'une solution temps polynomiale connue. (En fait, après avoir écrit ceci, je ne serais pas surpris que ce soit le cas, mais j'aimerais un retour d'information de la part d'un guru).

Answer 1

Théorème de Cook

La classe NP peut être définie comme la classe de problèmes décidables par une machine de Turing non déterministe en temps polynomial. Ce théorème montre que SAT est NP-complet en codant le fonctionnement de toute machine de Turing non déterministe par une formule booléenne, de telle manière que la machine accepte si et seulement si cette formule est SATisfiable.

Historiquement, la notion de NP-complétude a été introduite dans l'article fondateur de Richard Karp ( Réductibilité parmi les problèmes combinatoires ), où il a défini la NP-complétude, a utilisé le théorème de Cook et, en une seule fois, a révélé 21 problèmes NP-complets.

Answer 2

Pour vous donner l’essence de la preuve (c’est-à-dire plusieurs pages consacrées à la Ordinateurs et à l’Intractibilité de Garey & Johnson ):

Tout problème de calcul peut être exprimé sous la forme d'une machine de Turing.

Il est possible d’exprimer la machine de Turing sous forme de problème logique, satisfaisant certaines contraintes de complexité.

Par conséquent, si vous pouvez résoudre le problème de logique en temps polynomial, vous pouvez résoudre le problème de la machine de Turing en temps polynomial.

Ceci (avec quelques autres considérations) montre que si vous pouvez résoudre le problème de logique en temps polynomial, vous pouvez résoudre tout problème de NP en temps polynomial. Ceci étant la définition de NP-complet, le problème logique est donc NP-complet et peut servir de base à d’autres problèmes.

Le problème de logique utilisé s'appelle Satisfiability (souvent abrégé en SAT). Étant donné une série de clauses de la forme (A ou non-B ou non-C) (clauses consistant en un nombre quelconque de propositions et de négations de propositions reliées par un logique ou), existe-t-il une attribution de valeurs de vérité aux propositions qui rend toutes les clauses vraies?

La NP-complétude est une propriété bien définie. La seule raison pour laquelle vous doutiez d'un problème lié à NP-complete est que vous pensiez pouvoir y réduire un autre problème, mais que vous n'avez pas encore trouvé de problème pratique ni obtenu de preuve.

La question n'est pas de savoir s'il existe des problèmes NP-complets ou comment prouver un problème est NP-complet, mais ce que cela signifie. Personne n'a encore produit d'algorithme en temps polynomial pour résoudre un problème NP-complet, et personne n'a prouvé qu'un tel algorithme ne pouvait pas exister. Que ce soit ou non P = NP, nous n’avons certainement pas de bons algorithmes pour résoudre tout problème NP-complet.

C’est l’un des problèmes du Millénaire de la Fondation Claypool, donc si vous pouvez trouver une preuve qui échappe à des personnes très brillantes depuis quelques années, vous aurez droit à un million de dollars.