Υπολογιστική Πολυπλοκότητα 23-24 (CEID_NY302)

Ιστολόγιο

25 Διάλεξη (30/05/2024): Ασκήσεις σε NP-Πληρότητα

Πέμπτη, 30 Μαΐου 2024 - 6:48 μ.μ.
- από τον χρήστη Τσίχλας Κωνσταντινος

Ύλη:

  1. Αναγωγή από Κομβικό Κάλυμμα σε Κάλυμμα Συνόλου
  2. Αναγωγή από 3SAT σε MAX2SAT
  3. Αναγωγή με περιορισμό από ΑΘΡΟΙΣΜΑ_ΥΠΟΑΚΟΛΟΥΘΙΑΣ σε KNAPSACK

Υλικό:

Διαφάνειες σελ. 16-20, 36-38 (Οι αναγωγές από 3SAT σε ΑΘΡΟΙΣΜΑ_ΥΠΟΑΚΟΛΟΥΘΙΑΣ και από 3SAT σε HAMPATH είναι εκτός ύλης)

 0   0
Σχόλια (0)