Calculabilité et complexité [Résolu/Fermé]

Signaler
Messages postés
16
Date d'inscription
lundi 25 février 2008
Statut
Membre
Dernière intervention
9 janvier 2016
-
Messages postés
14675
Date d'inscription
vendredi 14 mars 2003
Statut
Modérateur
Dernière intervention
4 juillet 2020
-
Bonjour,


j'ai quelques questions concernant la calculabilité et complexité, j'ai du mal a répondre:
1-Que signifie être indécidable pour un problème donné?(donnez un exemple)
2-pourquoi considérer des machines de turing avec un alphabet {0,1,#} ne nuit pas à la généralité des résultat?
3-Soit A et B, que signifie réduire A à B?
4-Etant donné un problème, que signifie être complet pour une classe de complexité donnée?
Je sais que c'est bizarre comme demande :P
Merci :)

1 réponse

Messages postés
14675
Date d'inscription
vendredi 14 mars 2003
Statut
Modérateur
Dernière intervention
4 juillet 2020
235
Selon le théorème de CCM, toute demande d'aide au devoir finit implacablement plongée dans les profondeurs des messages hors sujets.
Sur ce, je vous invite à prendre connaissance de cette information concernant vos demandes de devoirs.

Si c'est votre exercice, c'est que la réponse se trouve dans vos cours.
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 63006 internautes nous ont dit merci ce mois-ci