Section outline

    • Skills

      •     Theoretical background
        •         know that a computational model called the Turing Machine exists, and that it is the reference model
      •     Vocabulary
        •         Identify a decision problem and an optimisation problem
        •         be able to write down the decision problem associated with an optimisation problem and vice versa
        •         know the definitions of the classes P and NP and their inclusion relations, and the associated conjecture
      •     NP-completeness
        •         know how to prove that a problem is in NP
        •         know how to prove that a problem is NP-hard
      •     SAT and 3-SAT
        •         Know the definitions of SAT and 3-SAT problems
        •         Know that they are NP-complete
      •     Hamiltonian circuit, Hamiltonian cycle and TSP  
        •         Know the definitions of Hamiltonian circuit, Hamiltonian cycle and TSP problems
        •         Know that they are NP-complete and be able to redo the proof for TSP
      •     Clique, Coloration, 3-coloration
        •         Know the definitions of these problems
        •         Know that they are NP-complete and be able to redo the proof for Clique
      •     co-NP class
        •         Know the definition of the complexity class
        •         Know how to prove that a problem is in co-NP
        •         Know an example of a problem in co-NP
    • complexity course notes File
      Not available unless: You belong to ORCO 24-25
    • Ressources


      Vidéos

    • "SAT : l'anneau unique pour les gouverner tous !"
    • 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