Le nombre de problèmes de NP-complets est-il fini?

Question

Il devrait être directement avancé pour montrer qu'il existe infiniment de nombreux problèmes durs NP:

Preuve: Prenez le problème Supprimer 1 Vertex 3-Col ( $ R1V3Col $ ) qui prend un graphique $ G= (v, e) $ comme une instance et donne une réponse oui iff un sommet $ x \ in v $ existe à partir de < span class="math-conteneur"> $ v $ donne un nouveau graphique $ g '= (v \ backslash \ {x \ {(u, v ) \ in e \, | \, u \ neq x \ terres v \ neq x \} $ qui est une instance positive de $ 3Col $ .

$ R1V3COL $ peut en effet être réduit à un problème de 3 colorabilité (qui est prouvé pour être complet) par (à titre d'exemple de réduction) enlever simplement un sommet de $ g $ et tester si $ g $ est 3-colorable. Si $ g $ n'est pas 3-colorable supprimer un autre sommet de $ g $ et testez-le. Répétez la répétition jusqu'à ce qu'il ne reste plus de sommets pour les tests.

Par conséquent, nous savons $ R1V3COL $ est un problème de NP-dur.

nous pouvons maintenant réduire $ R2V3Col $ à un $ R1V3COL $ problème (par un concept similaire comme indiqué ci-dessus pour $ R1v3col $ à $ 3Col $ pour montrer que $ R2V3Col $ est dans NP-DUR et ainsi de suite pour chaque Suppression de N SUPERTIS 3-COL problème. En d'autres termes, nous pouvons toujours réduire $ R (n) v3col $ à $ r (n-1) v3col $ . Par conséquent, nous savons qu'il doit y avoir une infinité de nombreux problèmes np-dur et nous sommes terminés.

maintenant à mon lemme: Je ne peux pas penser à une simple preuve pour montrer qu'un certain problème avec infiniment de variations (comme $ r (n) v3col $ ) est également en np pour prouver np-complétude et prouve donc que d'infiniment de nombreux problèmes sont dans la sous-classe NP-complète.

Answer 1

Comme dans le commentaire, considérez la collecte de problèmes $ n $ -sat (est $ \ phi $ , une formule logique dans $ n $ -cnf, satisfiatable?).Ou $ n $ $ -coloring des graphiques, pour $ n \ ge 3 $ (peut-il être coloré?avec N $ N $ couleurs?).De nombreux problèmes NP-Terminal ont un paramètre (y a-t-il une clique de taille $ K $ dans le graphique? A le digraphe un retour de sommet de la taille $ K $ ?).

Answer 2

Pour chaque entier K, prenez le problème du vendeur itinérant avec N> 1 villes où n est une puissance de k.(Choisis le problème de cette façon, car toutes les instances sont distinctes, nous pouvons donc dire avec une bonne conscience que ce sont des problèmes distincts).