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

Question

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

« La meilleure façon de prouver que certains nouveau problème est NP-complet est d'abord prouver qu'il est dans NP, puis de réduire un problème NP-complet connu il »

je suis sûr que je comprends: Si j'ai un problème, je peux montrer qu'il est NP-complet si je:

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

2. Afficher déjà connu un problème NP-complet peut être « réduit » au nouveau problème

Alors, ma question est, comment ont été les premiers NP- Compléter les problèmes «prouvés» pour être NP-complet? À un moment donné, l'ensemble des problèmes NP-complets connus devait être nul, ce qui aurait rendu impossible le recours à l'étape 2 dans le processus ci-dessus. Cela me fait penser qu'il existe une méthode différente pour la preuve dont je ne suis pas au courant. Soit cela, ou peut-être que toute la propriété NP-complete est "supposée" pour certains problèmes en raison de l'absence d'une solution de temps polynomiale connue. (en fait, après avoir écrit ceci, je ne serais pas surpris si c'est le cas, mais je voudrais des commentaires de gourou de toute façon).

Answer 1

Cook's Theorem

La classe NP peut être définie comme la classe des problèmes décidables par une machine de Turing non déterministes en temps polynomiale. Ce théorème montre que SAT est NP-complet en codant le fonctionnement de n'importe quelle 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 parlant, la notion de NP-complet a été présenté dans un article fondateur de Richard Karp (Reducibility Among Combinatorial Problems), où il a défini NP-complet, utilisé le théorème de Cook, et dans un grand coup, prouvé 21 problèmes NP-complets.

Answer 2

Pour vous donner l'essence de la preuve (qui est plusieurs pages de disque allant dans Garey & Les ordinateurs de Johnson et Intractibility):

Tout problème de calcul peut être exprimé comme une machine de Turing.

Il est possible d'exprimer la machine de Turing comme un 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. Cela (ainsi que d'autres considérations) montre que si vous pouvez résoudre le problème de logique en temps polynomial, vous pouvez résoudre n'importe quel problème NP en temps polynomial. Ceci étant la définition de NP-complet, le problème logique est donc NP-complet, et peut être utilisé comme base pour d'autres problèmes.

Le problème logique utilisé est appelé 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 logiques ou), y a-t-il une attribution de valeurs de vérité aux propositions les clauses vraies? NP-complétude est une propriété bien définie. La seule raison pour laquelle vous auriez des doutes sur un problème NP-complet est que vous pensiez pouvoir réduire un autre problème NP-complet, mais que vous n'avez pas réussi à trouver un problème ou à en tirer une preuve. La question n'est pas de savoir si des problèmes NP-complets existent, ou comment prouver qu'un problème est NP-complet, mais ce que cela signifie. Personne n'a encore produit un algorithme polynomial-temps pour résoudre un problème NP-complet, et personne n'a prouvé qu'un tel algorithme ne peut pas exister. Que P = NP ou non, nous n'avons certainement pas de bons algorithmes pour résoudre un problème NP-complet. Ceci est l'un des problèmes du Millénaire de la Fondation Claypool, alors si vous pouvez trouver une preuve qui a échappé à certaines personnes très brillantes pendant plusieurs années, il y a un million de dollars pour vous.