Imaginons un problème complexe, dans lequel on peut discriminer différents sous-problèmes (dans un graphe? on doit pouvoir porter ce problème dans un graphe). Il ne s'agit pas seulement d'identifier les parties polynomiales dans un problème, mais de littéralement exclure du problème principal les parties tautologiques/contradictoires (comme des portions de problèmes similaires au principe des tiroirs/nids de pigeon) résistantes aux heuristiques. Ainsi, le problème résultant est mieux exposé aux heuristiques. Qu'est-ce qui caractérise les problèmes tautologiques (problème et tautologie sont quelque peu antinomiques)? Comment les identifier et éviter d'avoir à les calculer? Comment reconnaître une tautologie sur la forme générale d'un problème sans avoir à passer par le problème TAUTOLOGIE (co-NP-complet)? Par récurrence? - tautologie vérifiée au 1er rang - tautologie prouvée au rang suivant ==> tautologie sur l'ensemble du problème jusqu'à un point donné Cette technique doit pouvoir s'étendre sur la forme générale d'autres énoncés (ce ne sont plus des problèmes si on a prouvé que leur énoncé est tautologique, faire des calculs sur de tels énoncés est une pure perte de temps). Un objet sans relation peut certes exister, mais il ne vaut pas la peine d'être representé (existe-t-il dès lors?). Arithmétique des problèmes. Exemple: SAT + TAUTOLOGIE = SAT. On peut classifier les problèmes de décision de NP-C en fonction l'opération atomique qu'ils représentent puis composer ces opérations pour créer de nouveaux problèmes. Exemple: partition(), bin_packing(), clique()... BIPARTI = partition(clique())... La preuve par récurrence est une règle d'inférence sur des ensembles dénombrables. L'argument diagonal est une règle d'inférence sur des ensembles indénombrables.