ER 05 (2011) : Complexité algébrique, complexité de comptage et applications en physique statistique

Dates :07-11/02

Horaires :
  • Lundi : 9h-12h15 et 14h-17h15 (Arnaud)
  • Mardi : 9h-12h15 (Jesper) et 14h-16h (Guillaume)
  • Mercredi : 9h-12h15 (Jesper) et 14h-16h (Guillaume)
  • Jeudi : 9h30-12h45 (Sylvain) – rien l’après-midi
  • Vendredi : 9h30-12h45 (Sylvain) et 14h30-16h30 (Guillaume) + QCM 20min
Intervenants :
  • Arnaud Durand (Equipe de logique mathématique, université Paris 7)
  • Jesper Jacobsen (Laboratoire de Physique Théorique, ENS)
  • Guillaume Malod (Equipe de logique mathématique, université Paris 7)
  • Sylvain Perifel (LIAFA, université Paris 7)

Correspondant local : Pablo Arrighi

Programme :

Le cours s'articulera autour de deux questions centrales en complexité :

  • Peut-on compter efficacement le nombre de solutions d’un problème ? (p. ex. combien d’affectations satisfont une formule booléenne ?)
  • Combien d’additions et de multiplications sont nécessaires pour calculer un polynôme ? (p. ex. peut-on calculer le permanent en un nombre polynomial d’opérations ?)
Nous verrons les liens forts qui existent entre ces deux questions, et comment elles éclairent le 
reste de la théorie de la complexité booléenne en apportant la puissance d'outils algébriques.

Ces questions sont également importantes en physique statistique car les propriétés thermodynamiques 
d’un modèle statistique dérivent de la fonction de partition, qui est une somme pondérée sur 
un très grand nombre d’états microscopiques du système : le problème acquiert ainsi une nature 
combinatoire. Nous verrons donc l'approche des physiciens pour résoudre des problèmes réputés difficiles.

Plan prévisionnel :

1. Comptage booléen

- Classes de comptage : définitions, propriétés.
- Complétude du permanent pour la classe #P.
- Propriétés de clôture.
- Théorème de Toda : compter est plus puissant qu'une alternance bornée de
  quantificateurs.

2. Physique statistique

- Physique statistique : pavages de dimères, entropie, etc.
- Comptage des appariements dans un pavage de dimères : résolution complète.
- Comptage des polygones autoévitants : approche numérique.
- Autres exemples par les matrices de transfert, phénomènes critiques.

3. Calcul de polynômes

- Classes algébriques : modèle de Valiant, classes VP et VNP, propriétés de
  base, complétude du permanent pour VNP.
- Variantes (avec ou sans constantes, degré borné ou non) : équivalence des
  différentes questions "VP=VNP?".
- Bornes inférieures (Baur-Strassen, polynômes ad-hoc, modèles restreints).
- Liens avec la complexité booléenne : comptage, calcul en espace
  polylogarithmique, dérandomisation...

Comments are closed.