Une machine de Turing autorisée à lire et à écrire des symboles d'un alphabet infini est-elle plus puissante qu'une MT régulière (c'est la seule différence, la machine a toujours un nombre fini d'états)? L'intuition me dit que non, car il faut un nombre infini d'états pour différencier chaque...
Je m'intéresse à l'auto-réductibilité du problème du graphique 3-Coloralibity. Définition du problème du graphique 3-Coloralibity. Étant donné un graphe non orienté , existe-t-il un moyen de colorer les nœuds en rouge, vert et bleu afin qu'aucun nœud adjacent n'ait la même couleur?GGG Définition de...
Nous venons donc d'apprendre sur l'auto-réductibilité en classe. Mon professeur et notre manuel ne s'engageraient pas à dire que tous les problèmes de NP sont auto-réductibles, mais il ne semble pas y avoir d'exemples de problèmes qui ne le soient pas. Je me demandais s'il y avait des exemples, ou...
C'est une tâche du concours informatique allemand ("Bundeswettbewerb Informatik"), mais comme la date limite est passée, poser cette question n'est pas une tricherie. Étant donné un graphique orienté pondéré par les sommets G = ( V, E)g=(V,E)G=(V, E) et valeurs cvcvc_v, trouver un sous-ensemble de...