Problème NP-complet indécidable

[invite997f7e79]

Bonjour,

est-ce que NP-complet == indécidable ?

Donnez un exemple de problème NP-complet indécidable pour l'expliquer.

Merci bcp de votre aide
-----

[invite7a8ce750]

Bonjour,

est-ce que NP-complet == indécidable ?

Donnez un exemple de problème NP-complet indécidable pour l'expliquer.

Merci bcp de votre aide

Jolie la question de cours.
T'en a une autre ?

[invite0cea7419]

un problème NP-complet est forcément décidable.

Les problèmes NP-complets sont, si on veut, les plus durs de la classe NP. Et par définition, un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...

Faut revoir ton cours, mon vieux

[invitedf667161]

Ca pète sec ici !

[A voir en vidéo sur Futura]

[invite997f7e79]

un problème NP-complet est forcément décidable.

Les problèmes NP-complets sont, si on veut, les plus durs de la classe NP. Et par définition, un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...

Faut revoir ton cours, mon vieux

Tout d`abord, merci de votre réponse!
un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...Oui, je suis d'accord,
Mais, on ne dit pas que NP == NP-complet.
le problème TSP est un problème NP-hard,un cycle est decidable si c'est un cycle hamiltonien , mais si c'est le plus petit cycle hamiltonien est indécidable.
alors... TSP est indécidable et NP-complet ?

[invite9cf21bce]

Salut !

mais si c'est le plus petit cycle hamiltonien est indécidable.

Ben non, savoir si un cycle hamiltonien donné de longueur n est le plus petit cycle hamiltonien (pour des poids donnés) n'est pas indécidable, même par une machine déterministe. Il suffit de regarder, partant d'un sommet donné, tous les parcours de longueur n. C'est lourd, mais décidable.

Tu peux préciser ce que tu entends (dans le cas des graphes finis bien sûr) ?

Taar.

[invite997f7e79]

Salut !



Ben non, savoir si un cycle hamiltonien donné de longueur n est le plus petit cycle hamiltonien (pour des poids donnés) n'est pas indécidable, même par une machine déterministe. Il suffit de regarder, partant d'un sommet donné, tous les parcours de longueur n. C'est lourd, mais décidable.

Tu peux préciser ce que tu entends (dans le cas des graphes finis bien sûr) ?

Taar.

Merci Taar.
Bon, c'est plus clair. Alors on peux dire que tous les problèmes NP-complet sont décidables ??
Ben, un problème indécidable alors n'est pas un problème NP-complet ??

[invite9cf21bce]

Exactement. NP-complet implique décidable. Je confirme ce que disait championnet.

Taar.

[invite0cea7419]

Les Problèmes NP-complets forment une partie de l'ensemble des problèmes NP (ce sont, en gros, les "plus durs").

Au passage, pour reprendre ton raisonnement sur les circuits hamiltoniens, il faut être prudent : être NP-dur ne signifie pas forcément être NP-complet. En effet, un problème est NP-complet si :

1. Il est NP-dur
2. Il est dans NP

Suivant les cas, c'est l'une ou l'autre des propriétés qui est dure à prouver. Un problème dans une classe supérieure à NP (genre, PSPACE, EXPTIME, etc.) sera évidemment NP-dur. Mais il ne sera pas dans NP.

En gros, dire qu'un problème est dans NP donne une borne supérieure sur sa complexité. Dire qu'il est NP-dur donne une borne inférieure (il est "au moins aussi dur que n'importe quel autre dans NP").

Des problèmes indécidables peuvent être NP-dur (voire même : ils le sont tous ? à vérifier. A priori le problème de l'arret des machines de Turing, indécidable, est NP-dur). Par contre ils ne peuvent pas être dans NP, parce que sinon ils seraient décidables.

Encore une fois, je ne peux que tu suggérer de prendre un manuel/cours de complexité, et de bien lire les définitions, car à mon avis tout ceci est encore un peu flou pour toi....

bon courage en tout cas !

[invite997f7e79]

très bonne réponse.
Merci à Taar,championnet !!!

[invite997f7e79]

Merci à Taar,championnet

Je me pose une question peut-être ridicule,
pour moi :

Un probleme appartient a P s'il est decidable en temps polynomial

Un probleme appartient a NP si on peut verifier une reponse "candidate" en un temps polynomial.

alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets .

Merci d'avance!

[invite0cea7419]

Un problème NP est décidable, c'est ce que j'ai dit 2 fois dans 2 messages différents au dessus

Voici comment :
1) détermine (une borne supérieure sur) la taille du candidat, qui est une fonction polynomiale de la taille de l'entrée (par définition)
2) énumère tous les candidats possibles de cette taille-là
3) utilise le fait qu'on peut décider en temps polynomial si un candidat est bon sur tous les candidats. Si l'un d'entre eux est un bon candidat, tu as ta réponse. S'ils sont tous de mauvais candidats, tu as ta réponse aussi.

ça termine en un temps exponentiel en la taille des candidats.

Pour la deuxième partie de ta reflection ("alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets.")

Déjà, d'un point de vue grammatical, cette question st louche

AUCUN problème indécidable n'est NP-complet tout simplement parce que être NP-complet implique être dans NP implique être décidable (cf. raisonnement ci-dessus).

J'espère que je suis clair ?

[invite997f7e79]

Un problème NP est décidable, c'est ce que j'ai dit 2 fois dans 2 messages différents au dessus

Voici comment :
1) détermine (une borne supérieure sur) la taille du candidat, qui est une fonction polynomiale de la taille de l'entrée (par définition)
2) énumère tous les candidats possibles de cette taille-là
3) utilise le fait qu'on peut décider en temps polynomial si un candidat est bon sur tous les candidats. Si l'un d'entre eux est un bon candidat, tu as ta réponse. S'ils sont tous de mauvais candidats, tu as ta réponse aussi.

ça termine en un temps exponentiel en la taille des candidats.

Pour la deuxième partie de ta reflection ("alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets.")

Déjà, d'un point de vue grammatical, cette question st louche

AUCUN problème indécidable n'est NP-complet tout simplement parce que être NP-complet implique être dans NP implique être décidable (cf. raisonnement ci-dessus).

J'espère que je suis clair ?

salut,

c'est très clair !!!!!!!!

[invitefb3d77a8]

Bonjour,

J'interviens en retard dans la discussion. Les arguments de chamionnet et Taar sont très clairs. Cependant je me pose une question par rapport à la conjecture P=NP, elle même indécidable. Apparemment, on peut démontrer qu'un problème P-complet est indécidable, donc un problème indécidable peut être exprimé sous forme P complète:
http://www2.lifl.fr/~delahaye/HECI/Calcul.pdf
Dès lors le fait que la réduction NP=P soit elle-même indécidable ne devrait-il pas à considérer qu contraire que l'on ne peut pas exclure à priori l'existence de problèmes à la fois NP-complets et indécidables?

[gg0]

par rapport à la conjecture P=NP, elle même indécidable

Tu es vraiment sûr de ça ?

Cordialement.

[invite0bbe92c0]

J'interviens en retard dans la discussion

Meuh non : juste 7 ans; une paille