M1, 2005–2006

Complexité structurelle – TD 9 Classes de comptage, suite

Exercice 1 FewP est l’ensemble des langages reconnus par machines non-déterministes polynomiales, ayant au plus un nombre polynomial de chemins acceptant. Montrer que FewP ⊆ ⊕P.

Un chemin hamiltonien dans un graphe non orienté est un chemin qui passe une fois et une seule par tous les sommets du graphe. Hamilton Path est le langage consistant des graphes possédant un chemin hamiltonien ; c’est un problème NP-complet. #Hamilton Path est la fonction qui à un graphe associe le nombre de ses chemins hamiltoniens. Exercice 2 On souhaite montrer #Hamilton Path est #P-complet.

1. Montrer que #Hamilton Path ∈ #P.

2. Comprendre la réduction de 3SAT à Hamilton Path sur les figures jointes (figures A1 et A2). Pourquoi n’est-elle pas parcimonieuse ? Pourquoi n’est-ce pas une réduction de #3SAT à #Hamilton Path ?

3. Expliquer le fonctionnement des gadgets « diamant » et du « non-et » (figures B2 et B3).

4. En s’aidant des figures B, montrer que #Hamilton Path est #P-complet.