Mif09 - Modèles de calcul et complexité

ANNEE 2024 - 2025

Modèles de calcul et complexité

Page pédagogique de l’UE Mif09 - modèles de calcul et complexité

Partie complexité

Mardi 11 mars 2025 09h45 - CM classe P et NP

• [M1if09-CM07.pdf]

Mardi 18 mars 2025 08h00 - TD classe P

• Rappels P et NP
• Shift est linéaire
• P est stable par complément
• 2-SAT est P
• 2-COL est P

Mardi 18 mars 2025 09h45 - CM NP-complétude

• [M1if09-CM08.pdf]

Mardi 18 mars 2025 11h00 - TD classe NP et NP-complétude

• Rappels réduction polynomiale et NP-complet
• Supposons qu’on a une réduction polynomiale d’un problème P1 vers un problème P2
  1. Si P1 est dans P, est-ce que P2 est dans P ?
  2. Si P2 est dans P, est-ce que P1 est dans P ?
  3. Si P1 est NP-complet, est-ce que P2 est NP-complet ?
  4. Si P2 est NP-complet, est-ce que P1 est NP-complet ?
  5. Si on connait une réduction polynomiale de P2 vers P1, est-ce que P1 et P2 sont NP-complets ?
  6. Si P1 et P2 sont NP-complets, est-ce qu’il existe une réduction polynomiale de P2 vers P1 ?
  7. Si P1 est dans NP, est-ce que P2 est NP-complet ?
• 2-COL dans P par réduction à 2-SAT
• 3-SAT NP-complet par réduction depuis SAT
• 3-COL NP-complet par réduction depuis 3-SAT