Discussion:Réduction (complexité)
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Informatique théorique.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | À évaluer |  | Informatique théorique (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Commentaires de Pierre de Lyon, copiés depuis la discussion du portail modifier
- D'autre part, la phrase d'introduction devrait dire en mots simples à quoi sert la réduction d'un problème à un autre.
- Dans les exemples je parlerais aussi de la réduction pour prouver l'indécidablité.
- Je dirais aussi que dans les chaînes de réduction, il faut partir d'un problème de référence: le problème SAT pour NP, l'indécidabilité de l'arrêt pour l'indécidabilité.
