Projet:ENS Rennes complexité

La version imprimable n’est plus prise en charge et peut comporter des erreurs de génération. Veuillez mettre à jour les signets de votre navigateur et utiliser à la place la fonction d’impression par défaut de celui-ci.

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