Εβδομάδα 12: Οι κλάσεις P και NP
Περιεχόμενο: Είδη προβλημάτων (στιγμιότυπο, πλανώδιος πωλητής (TSP), εικασίας fermat, υπολογισμός π, subset sum), κλάση P (προβλήματα RELPRIME, CSG), κλάση NP (Κύκλος Hamilton, μονοπάτι Hamilton, πιστοποιητικό), NP προβλήματα ικανοποίησης περιορισμών (SAT, λογική μεταβλητή, άρνηση λογικής μεταβλητής, όρος), άλλα προβλήματα NP κλάσης (Κλίκα, Node Cover, Edge Cover, KNAPSACK, 3Δ‐MATCHING, Independent Set, 2‐MACHINE SCHEDULING, 3COLORING, CHROMATIC NUMBER, πρόβλημα 3SAT και παραλλαγές του (1in3SAT, ΝΑΕ3SAT), 0 ‐ 1 integer integer programming, Υ/Ν TSP (πρόβλημα περιοδεύοντος πωλητή πρόβλημα περιοδεύοντος πωλητή ΠΠΠ), φράση και Κανονική Συζευκτική Μορφή (ΚΣΜ), αληθεύσιμη πρόταση, MAX CUT, SET (EXACT) COVER, PARTITION, BIN PACKING).
