Résumé de section


    • Compétences:

      1. Contexte théorique
        • savoir qu'un modèle de calcul appelé Machine de Turing existe, et que c'est le modèle de référence
      2. Vocabulaire 
        • Savoir identifier un problème de décision et un problème d'optimisation
        • Savoir écrire le problème de décision associé à un problème d'optimisation et vice-versa
        • connaître les définitions des classes P et NP et leurs relations d'inclusion, la conjecture associée
      3. NP-complétude
        • Savoir prouver qu'un problème est dans NP : algorithme vérifieur
        • Savoir prouver qu'un problème est NP-difficile : réduction
      4. SAT et 3-SAT 
        • Connaître les définitions des problèmes SAT et 3-SAT
        • Savoir qu'ils sont NP-complets
      5. Circuit Hamiltonien, cycle Hamiltonien et TSP  
        • Connaître les définitions des problèmes Circuit Hamiltonien, cycle Hamiltonien et TSP
        • Savoir qu'ils sont NP-complets et savoir refaire la preuve pour TSP
      6. Clique, Coloration, 3-coloration
        • Connaître les définitions des problèmes 
        • Savoir qu'ils sont NP-complets et savorir refaire la preuve pour Clique
      7. Classe co-NP
        • Connaître la définition de la classe de complexité
        • Savoir écrire un algorithme vérifieur pour un problème dans co-NP
        • Connaître un exemple de problème dans co-NP

       

       

    • One idea, one story: solving or proving? a $1 million question Page
      Les étudiants doivent
      Marquer comme terminé
    • Slides NP-completude by Aurélie Lagoutte (in French) Fichier
      Déposé le 27 août 24, 17:36
    • Slides NP-completude by Aurélie Lagoutte (in English) Fichier
    • Lecture notes for ORCO students (by P. Lemaire) Fichier
      Modifié 28 nov. 23, 07:38
    • complexity course notes Fichier
      Non disponible à moins que : Vous soyez membre de ORCO 24-25
    • Play with complexity functions Test
      Les étudiants doivent
      Recevoir une note
    • Problems Glossaire
      Les étudiants doivent
      Marquer comme terminé
    • Types of problems Test
      Les étudiants doivent
      Marquer comme terminé
    • Find the class Test
      Les étudiants doivent
      Marquer comme terminé
    • Fausses preuves de classe de complexité Page

    • Ressources


      Vidéos

    • An introductory video on P vs NP URL
    • A video to understand P=NP by Science étonnante (in french) URL
      "SAT : l'anneau unique pour les gouverner tous !"
    • A video on P vs NP by Passe-science (in French) URL
    • Undefined Behavior : A youtube playlist about P vs NP URL
    • Subset-Sum is NP-complete Page

    • Readings

      • Computers and Intractability: A Guide to the Theory of NP-Completeness, M.R. Garey, D.S. Johnson 
              (the reference book)
      • Computational complexity, C.H. Papadimitriou
      • A guide to algorithm design, A. Benoit, Y. Robert, F. Vivien
      • The Algorithm design manual, S. S. Skiena
              chap 9: Intractable Problems and Approximation Algorithms
      • Algorithms (Chap 8)  by Dasgupta, Papadimitriou and Vazirani

    • Web sites

    • The complexity zoo URL
    • The P vs NP page URL
    • A compendium of NP optimization problems, P. Crescenzi, and V. Kann (with approximation results) URL