Projet:ENS Rennes complexité

Les élèves du département informatique de l'ENS Rennes s'unissent pour améliorer certains articles wikipedia relatifs à la théorie de la complexité.

Pages à améliorer

• Création d'une page sur le jeu de géographie généralisé. Y mettre un exemple et la démo de la PSPACE-dureté.
• Mettre la démo que l'universalité d'une expression rationnelle avec complémentation est non élém sur Problème non élémentaire
• Parler de proba sur NL (complexité) (voir la version anglaise)
• Traduire https://en.wikipedia.org/wiki/SL_(complexity) (la classe définie pour USTCON)
• Rédiger la page sur le Problème d'accessibilité
• Rédiger la démonstration 2SAT est NL-complet sur Problème 2-SAT ?
• SC (complexité)
• Donner des exemples de problèmes sur Hiérarchie polynomiale
• Donner la démonstration que PEEK est EXPTIME-complet sur EXPTIME
• Donner des exemples et les définitions pour les différents types de réduction sur Réduction (complexité)
• Rédiger la section sur le théorème de Barrington dans l'article NC