Discussion :

[jkalzsmu]

Bonjour,

Petit question de théorie de la compléxité :
Existe t-il un problème de décision (décidable) qui n'appartient pas à la classe NP?

Question que je me posais tout à l'heure mais dont je n'ai pas trouvé d'exemple.

J'ai simplement trouvé dans google que la classe des problèmes de NP est inclue dans la classe des problèmes EXPTIME. Mais je n'ai pas trouvé d'exemple de EXPTIME.

[Furikawari]

Le fait d'être un problème décidable n'a pas de lien direct avec NP. "Est-ce que ce nombre est pair" est décidable et dans P.

Liste de problèmes NP

[jkalzsmu]

Certe mais P est inclu dans NP. Donc ce problème appartient bien à la classe NP.

[Furikawari]

Au temps pour moi ça m'apprendra à répondre trop vite. Du coup la seule chose dont je suis certain c'est que pb dans NP => pb décidable. J'ai posé la question à une personne compétente pour la réciproque (intuitivement je dirais qu'elle est fausse, mais je trouve pas d'exemple probant), je reviens vers toi dès que j'ai la réponse

[Furikawari]

Bon, voilà la réponse que j'ai eue...

en fait, il y a beaucoup de classes existantes au dessus de NP, avant d'arriver sur les non décidables :
PSPACE et EXPTIME par exemple.
Les inclusions strictes sont la plupart du temps des problèmes ouverts,
sauf par exemple P et PSPACE dont on sait qu'il existe un problème de PSPACE qui n'est pas dans P...
De mémoire, je crois que de même il existe des problèmes non décidables qui ne sont pas dans NP.
Si tu as besoin de choses plus précises, je peux creuser...

Bon y'a une petite erreur dans l'avant dernière phrase mais grosso modo : y'a rien de sûr.
En théorie la classe des problèmes décidables englobe celle de problèmes NP (modulo les inclusions strictes, problème ouvert comme il le dit, et donc rien n'empêche que décidable=NP comme rien n'empêche que P=NP), en pratique c'est pas gagné pour en citer un qui soit décidable et pas dans NP...

[jkalzsmu]

Ok, merci pour la réponse