Un problème fini peut-il être dans NP-Complete?

Mon conférencier a fait la déclaration

Tout problème fini ne peut pas être NP-Complete

Il parlait de Sudoku à l'époque en disant quelque chose dans le sens que pour un Sudoku 8x8, il existe un ensemble fini de solutions, mais je ne me souviens pas exactement de ce qu'il a dit. J'ai écrit la note que j'ai citée mais je ne comprends toujours pas vraiment.

Les Sudoku sont NP complets si je ne me trompe pas. Le problème de clique est également NP-Complete et si j'avais un problème 4-Clique, n'est-ce pas un problème fini qui est NP-Complete?

np-complete np TheRapture87
la source

Qu'est-ce qu'un «problème fini»? Google et Wikipedia n'aident pas.

Anton Trunov

@AntonTrunov Un problème dans lequel l'entrée a une longueur limitée.

Yuval Filmus

@YuvalFilmus, n'est-ce pas vrai pour toutes les paires d'entrées valides de la machine Turing *? IIRC l'un des symboles est désigné comme le symbole vierge et l'entrée a initialement une région délimitée en dehors de laquelle des symboles autres que le symbole vierge ne peuvent pas apparaître. Le terme "NP complet" n'est généralement pas utilisé dans le contexte des opérations sur des flux qui ne peuvent pas être modélisés sans assouplir cette hypothèse.

Mike Samuel

@MikeSamuel Quand je dis longueur bornée, je veux dire entrée de taille au plus 100. (Ou tout autre nombre que 100.)

Yuval Filmus

@YuvalFilmus, ok. Je dis, le terme "NP complet" n'est utilisé que lorsqu'il n'y a pas de symboles non vides sur l'entrée ou qu'il existe un nombre entier qui est le nombre de symboles entre le symbole non vide le plus à gauche et le symbole non vide le plus à droite . 100 serait un tel exemple.

Mike Samuel

Réponses:

Si un problème fini est NP-complet alors P = NP, car chaque problème fini a un algorithme à temps polynomial (même un algorithme à temps constant).

Lorsque nous disons que Sudoku est NP-complet, nous voulons dire qu'une version généralisée de Sudoku joué sur une carte est NP-complète. $n^2 \times n^2$

Enfin, le problème des 4 cliques, bien qu'il ne soit pas un problème fini (le graphe d'entrée a une taille illimitée), est un problème facile qui a un algorithme de temps polynomial.

Yuval Filmus
la source

Le problème des 4 cliques est-il donc P puisqu'il a un algorithme polynomial temporel?

TheRapture87

@ Aceboy1993 Oui, c'est la définition de P.

Yuval Filmus

Mais alors pourquoi K-clique est-il considéré comme étant dans NP-Complete? Est-ce que K ne représente pas seulement un nombre comme 4?

TheRapture87

k

$k$

k

$k$

De plus, nous pouvons prouver que Clique est NP-complet.

Yuval Filmus

La déclaration de votre professeur est incorrecte ou vous ne l'avez probablement pas entendu correctement. La déclaration correcte est

$L$ $|L| \geq 1$ $P = NP$

$P \neq NP$ $|L|>1$ $\emptyset$ $P=NP$ $P \neq NP$

Le Sudoku ou les échecs ne sont pas complets (comme Yuval l'a souligné), car leur entrée est une carte de taille finie 9x9 ou 8x8 (je parle des versions de décision, si le sudoku a une solution ou si les échecs ont une stratégie gagnante). Aux échecs, je suppose que si vous répétez une position, elle est considérée comme un match nul.

Shreesh
la source

Rappel: Un problème X est NP-complet s'il satisfait à deux critères:

a) C'est en NP - c'est-à-dire que toute solution supposée de X peut être vérifiée en temps polynomial.

b) Il est complet pour NP - Ie Chaque problème Y dans NP a une réduction du temps polynomial qui traduit une instance de Y en une instance de X (de sorte que tout programme polynomial qui résout X résoudrait également Y en temps polynomial) ).

Nous pouvons convenir qu'un Sudoku 9x9 satisfait (a). C'est (b) où les choses tombent. Plus généralement - Les problèmes (en NP ou autre) ont généralement des instances de taille N pour des valeurs arbitrairement grandes de N ; cela est certainement vrai pour les problèmes connus de NP. Une réduction d'un tel problème à un qui a une taille de problème maximale possible ne pourrait pas être une réduction d'instance à instance valide, car la première a toujours (infiniment) plus d'instances que la seconde. C'est pourquoi Sudoku doit être généralisé aux matrices NxN avant de pouvoir considérer l'exhaustivité de NP.

PMar
la source

Ce n'est pas correct. Il est parfaitement possible d'avoir une réduction valide d'un problème avec une infinité d'instances à un problème avec un nombre fini d'instances. Par exemple, voici une réduction de SAT au problème de déterminer si une chaîne de longueur 1 est égale à "a": si l'instance SAT est satisfaisable, mappez-la à la chaîne "a"; sinon, mappez-le à la chaîne "b". Maintenant, cette réduction (probablement) n'est pas calculable en temps polynomial mais c'est une réduction parfaitement valide.

David Richerby