Calculabilité et complexité
Résolu/Fermé
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 :)
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
-
ModérateurSelon 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.
