En ce qui concerne les problèmes des classes non polynomiales sur machine déterministe, il s'agit bien de problèmes décidables, mais pas en temps/espace raisonnables (au moins l'un des deux croit exponentiellement avec la taille du problème). Ceci dit, on est quand même bien contents qu'ils existent, ces problèmes, pour la cryptographie.
[^] # Re: Programmer une IA ou ....
Posté par scand1sk (site web personnel) . En réponse au journal quels ouvrages de référence sur les IA ?. Évalué à 1.
En ce qui concerne les problèmes des classes non polynomiales sur machine déterministe, il s'agit bien de problèmes décidables, mais pas en temps/espace raisonnables (au moins l'un des deux croit exponentiellement avec la taille du problème). Ceci dit, on est quand même bien contents qu'ils existent, ces problèmes, pour la cryptographie.