NP-πλήρες

Ο επιστάτης ενός πανεπιστημίου θα πρέπει να κάνει φωτοαντίγραφα εργασιών που θα μοιραστούν την επόμενη μέρα. Το πρωί λοιπόν δίνονται στον επιστάτη οι εργασίες καθώς και το πλήθος των φωτοαντιγράφων για κάθε μια από αυτές. Ο επιστάτης μπορεί να χρησιμοποιήσει τρία φωτοαντιγραφικά μηχανήματα (θα τα ονομάζουμε Χ, Υ και Ζ εφεξής). Η πολιτική του πανεπιστημίου είναι κάθε εργασία να δίνεται προς αντιγραφή σε ένα μόνο από τα τρία μηχανήματα (σε όποιο επιλέξει ο επιστάτης) ενώ από τη στιγμή που θα αρχίσει μία εργασία να φωτοτυπείται θα πρέπει να δημιουργηθούν όλα τα αντίγραφά της χωρίς διακοπές. Δεν επιτρέπεται δηλαδή να εκτυπώνουμε κάποια αντίγραφα της εργασίας Α, μετά της εργασίας Β και μετά πάλι της Α στο ίδιο μηχάνημα, αλλά από τη στιγμή που θα ξεκινήσει η εργασία Α να εκτυπώνεται θα πρέπει να δημιουργηθούν όλα τα απαραίτητα αντίγραφά της. Ο χρόνος αντιγραφής μίας εργασίας είναι ανάλογος του πλήθους των φωτοαντιγράφων που απαιτούνται. Ο επιστάτης θέλει να φτιάξει ένα σχέδιο κατανομής των εργασιών στα τρία μηχανήματα με στόχο να ελαχιστοποιήσει το χρόνο ολοκλήρωσης όλων των φωτοαντιγράφων, ώστε να πάει νωρίτερα σπίτι του. Στη χειρότερη περίπτωση, ο χρόνος ολοκλήρωσης δεν πρέπει να ξεπερνά ένα χρονικό άνω όριο, έστω k. Προσοχή, ασχολούμαστε μόνο με το χρόνο της αντιγραφής και όχι με τους υπόλοιπους χρόνους που αφορούν τη διαχείρισή τους, όπως μεταφορά των αντιγράφων, γέμισμα με χαρτί των μηχανημάτων, επίλυση των εμπλοκών χαρτιού κοκ.

Για παράδειγμα, ας υποθέσουμε ότι για τις εργασίες Α, Β, Γ, Δ και Ε απαιτούνται 10, 5, 20, 20 και 15 φωτοαντίγραφα αντίστοιχα. Τότε ο επιστάτης θα μπορούσε στο Χ να βάλει τις εργασίες Α και Β, στο Υ να βάλει τις εργασίες Γ και Ε και στο Ζ την εργασία Δ. Τότε, το Χ θα κάνει 15 αντίγραφα συνολικά, το Υ θα κάνει 35 αντίγραφα και το Ζ θα κάνει 20 αντίγραφα. Επομένως, ο επιστάτης θα πρέπει να περιμένει να τελειώσει το Υ τα 35 αντίγραφα για να φύγει. Αν όμως ο επιστάτης επέλεγε να κατανείμει τις εργασίες διαφορετικά ενδεχομένως να τελείωνε νωρίτερα. Πράγματι, αν έβαζε στο Χ τις Α και Ε, στο Υ τις Β και Γ και στο Ζ την Δ τότε θα έπρεπε να περιμένει για 25 αντίγραφα μόνο. Σας ζητούνται τα εξής:

Α) Βοηθείστε τον επιστάτη να μοντελοποιήσει το πρόβλημα του ως ένα πρόβλημα απόφασης, το οποίο θα ονομάσουμε ΕΕ (Έξυπνος Επιστάτης).

Υπόδειξη: Θυμηθείτε τα είδη προβλημάτων που παρουσιάζονται στην ενότητα 3.1 του Τόμου Β’.

Β) Αποδείξτε ότι το πρόβλημα ΕΕ ανήκει στην κλάση NP.

Γ) Αποδείξτε ότι το πρόβλημα ΕΕ είναι NP-πλήρες ανάγοντας σε αυτό οποιοδήποτε από τα προβλήματα συνόλων και αριθμών που αναφέρονται στις σελίδες 176-177 του Τόμου Β’, και μόνο από αυτά. Να είστε προσεκτικοί στην επιλογή του προβλήματος μιας και η ευκολία της αναγωγής εξαρτάται από αυτή την επιλογή. Παρατήρηση: Θεωρήστε ότι σε όλα αυτά τα προβλήματα οι εμπλεκόμενες ποσότητες (π.χ., στο πρόβλημα PARTITION, τα μεγέθη των αντικειμένων) είναι πάντα μη αρνητικοί ακέραιοι.

Δ) Πώς θα αλλάζατε την αναγωγή αν ο επιστάτης είχε στη διάθεσή του k>3 φωτοαντιγραφικά μηχανήματα; (Δώστε ένα σύντομο σχόλιο, χωρίς να δώσετε απόδειξη).