Citation de hallavar
Oui mais tous les NP peuvent se ramener à des algo de type NP complet. Donc si tu le montre pour un NP-complet, tu as gagné..
Mais en fait sur cette question de indécidable, ca dépend de l'arithmétique que tu choisis je crois. Et là je suis trop low IQ pour t'en parlé..

merci de preciser en vrai je sous entendais ca pour moi c'est pareil j'ai pas compris la difference c'est pas juste qu'il est plus dur ? l'indécidablilité de ce que j'ai compris c'est juste que l'on ne pourra jamais demontrer que c'est vrai ou faux c'est tout (dans les axiomes utilisés)