Κεφάλαιο 10Βασικά Στοιχεία Πολυπλοκότητας

Σε αυτό το κεφάλαιο θα ασχοληθούμε με τα όρια της αποδοτικότητας των αλγορίθμων. Τι σημαίνει όμως αποδοτικός αλγόριθμος (πάντοτε ως προς τη χρονική διάρκεια εκτέλεσης); Διαισθητικά θα λέμε ότι ένας αλγόριθμος είναι αποδοτικός, αν ο χρόνος εκτέλεσής του είναι λογικός σε συνάρτηση με το μέγεθος του γράφου που χειριζόμαστε. Αυτός ο ορισμός είναι βεβαιώς ανεπαρκής μιας και δεν έχουμε ορίσει τι σημαίνει ”λογικός”. Θα λέμε ότι ένας αλγοριθμος είναι αποδοτικός, αν η χρονική του πολυπλοκότητα είναι πολυωνυμική²²της μορφής $O(n^{\mathrm{\ell }})$, όπου $n$ είναι το μέγεθος της εισόδου και $\mathrm{\ell }$ μία θετική σταθερά. Στην περίπτωση των γράφων το μέγεθος της εισόδου καθορίζεται από το πλήθος των κορυφών $n$ και των ακμών $m$.

Από την άλλη πλευρά, υπάρχουν προβλήματα όπως αυτό της εύρεσης ενός Hamiltonian κυκλώματος³³Ένα Hamiltonian κύκλωμα σε ένα γράφημα $G$ είναι ένας κύκλος που διέρχεται μία και μόνο μία φορά από κάθε κορυφή του γραφήματος $G$. που δεν έχει βρεθεί αποδοτικός αλγόριθμος μέχρι σήμερα (εν έτει 2015) παρόλη την μεγάλη προσπάθεια που έχει γίνει. Όλοι οι αλγόριθμοι για αυτό το πρόβλημα που έχουμε μέχρι τώρα δεν είναι αποδοτικοί, με την έννοια ότι ο χρόνος εκτέλεσης τους είναι εκθετικός⁴⁴της μορφής $O\left(2^{\mathrm{\Omega }(n^{ϵ})}\right)$, όπου $n$ είναι το μέγεθος της εισόδου και $ϵ>0$ μία σταθερά. σε σχέση με το μέγεθος του γράφου εισόδου. Υπάρχουν πάρα πολλά προβλήματα που φαίνεται να μην επιδέχονται αποδοτικής λύσης. Σε αυτό το κεφάλαιο θα αναφερθούμε συνοπτικά στη θεωρία που καταπιάνεται με την ταξινόμηση αλγοριθμικών προβλημάτων με βάση τη σχετική δυσκολία τους, την Πολυπλοκότητα.

Μία από τις βασικές επιδιώξεις της θεωρίας πολυπλοκότητας είναι η ταξινόμηση των προβλημάτων σε κλάσεις πολυπλοκότητας ανάλογα με την φαινομενική δυσκολία τους. Αυτό που μας ενδιαφέρει δεν είναι μόνο η ταξινόμηση των προβλημάτων σε κλάσεις αλλά και η σχέση που υπάρχει μεταξύ διαφορετικών κλάσεων πολυπλοκότητας. Οι σχέσεις αυτές μας φανερώνουν βαθύτερες σχέσεις μεταξύ διαφορετικών μέσων υπολογισμού (π.χ. τυχαίοι αλγόριθμοι σε σχέση με αιτιοκρατικούς αλγόριθμους), ενώ αντίστοιχα προσφέρουν ένα μέτρο δυσκολίας των προβλημάτων που ανήκουν σε αυτές τις κλάσεις. Εμείς θα εστιάσουμε μόνο σε δύο κλάσεις - ίσως τις πιο γνωστές - την κλάση αιτιοκρατικού πολυωνυμικού χρόνου $𝒫$ (Polynomial) και την κλάση μη αιτιοκρατικού πολυωνυμικού χρόνου $𝒩𝒫$ (Non-deterministic Polynomial). Η πρώτη κλάση περιέχει όλα τα προβλήματα που μπορούν να επιλυθούν από έναν αιτιοκρατικό (deterministic) υπολογιστή σε πολυωνυμικό χρόνο. Ένα τέτοιο παράδειγμα προβλήματος είναι η εύρεση Eulerian κυκλωμάτων⁵⁵Ένα γράφημα $G$ έχει Eulerian κύκλωμα αν υπάρχει κύκλος που να διέρχεται από όλες τις ακμές μία και μόνο μία φορά. σε γραφήματα. Η δεύτερη κλάση περιέχει όλα εκείνα τα προβλήματα τα οποία μπορούν να λυθούν σε έναν μη αιτιοκρατικό (non-deterministic) υπολογιστή σε πολυωνυμικό χρόνο. Ένα τέτοιο παράδειγμα αποτελεί η εύρεση Hamiltonian κυκλωμάτων σε γραφήματα. Θα δούμε παρακάτω έναν πιο διαισθητικό ορισμό της κλάσης $𝒩𝒫$.

Ένα από τα μεγαλύτερα ανοικτά προβλήματα στην Επιστήμη των Υπολογιστών και στα Μαθηματικά είναι αν $𝒫\ne 𝒩𝒫$. Η πιο σημαντική προσπάθεια που έχει γίνει προς την κατεύθυνση επίλυσης αυτού του προβλήματος είναι η θεωρία $𝒩𝒫$-πληρότητας και πιο γενικά η θεωρία ύπαρξης χαρακτηριστικών προβλημάτων για αρκετές κλάσεις πολυπλοκότητας. Κατ’ αυτόν τον τρόπο, για μία κλάση πολυπλοκότητας $𝒳$ θα λέμε ότι ένα πρόβλημα είναι $𝒳$-πλήρες αν η πολυπλοκότητά τους καθορίζει και τη θέση της $𝒳$ στην ιεραρχία των κλάσεων πολυπλοκότητας.

Στη συνέχεια, θα δούμε πιο αναλυτικά τις βασικές κλάσεις πολυπλοκότητας και θα προσπαθήσουμε να αιτιολογήσουμε διαισθητικά τη σημασία τους ενώ ταυτόχρονα θα αναφερθούμε στην έννοια της πληρότητας. Πριν όμως μιλήσουμε για κλάσεις πολυπλοκότητας θα αναφερθούμε συνοπτικά σε ένα εξαιρετικό εργαλείο επίλυσης προβλημάτων, την αναγωγή.

Η θεωρία πολυπλοκότητας ασχολείται ως επί το πλείστον με συγκεκριμένο τύπο προβλημάτων. Ένα πολύ γνωστό πρόβλημα είναι το πρόβλημα του περιοδεύοντος πωλητή (Travelling Salesman Problem - TSP), το οποίο ορίζεται ως εξής:

Αυτό είναι ένα πρόβλημα βελτιστοποίησης, δηλαδή ένα πρόβλημα όπου μας ζητείται να βρούμε μία δομή (το Hamiltonian κύκλωμα στη συγκεκριμένη περιπτωση) που να μεγιστοποιεί (ή ελαχιστοποιεί) μία συγκεκριμένη ποσότητα (το άθροισμα των βαρών). Από την άλλη πλευρά, το πρόβλημα του Hamiltonian κυκλώματος είναι ένα πρόβλημα αναζήτησης μιας και μας ζητείται μία δομή (ένα κύκλωμα) που έχει μία συγκεκριμένη ιδιότητα (να είναι Hamiltonian). Η θεωρία πολυπλοκότητας από την άλλη ασχολείται κυρίως με προβλήματα απόφασης. Σε ένα πρόβλημα απόφασης η έξοδος της λύσης είναι δυαδική (ΝΑΙ/ΟΧΙ). Ο κυριότερος λόγος για αυτή την επιλογή είναι η απλότητα, χωρίς να σημαίνει βέβαια ότι δεν έχουν οριστεί και ερευνηθεί κλάσεις πολυπλοκότητας που να επιστρέφουν τιμή. Η μετατροπή ενός προβλήματος βελτιστοποίησης σε πρόβλημα απόφασης γίνεται εισάγοντας μία καινούργια μεταβλητή στο πρόβλημα απόφασης, που να αποτελεί άνω ή κάτω φράγμα για την ποσότητα που ελαχιστοποιείται ή μεγιστοποιειται αντίστοιχα στο πρόβλημα βελτιστοποίησης. Το πρόβλημα απόφασης του TSP ορίζεται ως εξής:

Προσέξτε ότι για αυτόν τον ορισμό αρκεί να σχεδιάσουμε ένα αλγόριθμο που να επιστρέφει ΝΑΙ, αν υπάρχει τέτοιο κύκλωμα αλλιώς θα επιστρέφει ΟΧΙ. Στη δεύτερη περίπτωση μπορεί να υπάρχει Hamiltonian κύκλωμα αλλά το συνολικό του βάρος να είναι μεγαλύτερο από $k$. Το γεγονός οτι από εδώ και στο εξής θα ασχοληθούμε με προβλήματα απόφασης αντί για τα αντίστοιχα βελτιστοποίησης δεν είναι καθόλου περιοριστικό όσον αφορά την απόδοσή τους. Πράγματι, αν έχουμε έναν αλγόριθμο για το πρόβλημα βελτιστοποίησης του TSP τότε για να λύσουμε το αντίστοιχο πρόβλημα απόφασης αρκεί να βρούμε την βέλτιστη λύση $OPT$ και να ελέγξουμε αν ισχύει $OPT\le k$. Η άλλη κατεύθυνση είναι λίγο πιο πολύπλοκη αλλά βασίζεται στην ιδέα της δυαδικής αναζήτησης πάνω στην τιμή $k$. Πιο συγκεκριμένα, έστω ότι έχουμε έναν αλγόριθμο ${𝒜}_d$ για το πρόβλημα απόφασης TSP. Έστω ότι $C$ είναι το μέγιστο βάρος στις ακμές του $G$. Τότε εφαρμόζουμε δυαδική αναζήτηση για την τιμή $k$ στο διάστημα $[0,nC]$ και για κάθε τέτοια τιμή εφαρμόζουμε τον ${𝒜}_d$. Αν επιστρέψει ο ${𝒜}_d$ ΝΑΙ, τότε συνεχίζουμε στο πάνω μισό του διαστήματος αναδρομικά, αλλιώς στο κάτω μισό. Αυτός ο αλγόριθμος ${𝒜}_o$ θα καλέσει συνολικά $\mathrm{{\rm O}}(\log nC)$ φορές τον ${𝒜}_d$. Άρα, αν ο ${𝒜}_d$ ήταν πολυωνυμικός αλγόριθμος τότε και ο ${𝒜}_o$ θα ήταν επίσης πολυωνυμικός. Αυτή η διαδικασία, δηλαδή, δείχνει ότι η απόδοση του προβλήματος βελτιστοποίησης θα είναι αρκετά κοντά στην απόδοση του αντίστοιχου προβλήματος απόφασης. Από αυτό το σημείο και στο εξής θα αναφερόμαστε μόνο σε προβλήματα απόφασης.

Το κυριότερο εργαλείο για να αποδείξουμε ότι ένα πρόβλημα ανήκει σε μία κλάση πολυπλοκότητας είναι η αναγωγή. Η ιδέα της αναγωγής είναι εξαιρετικά απλή και αναφέρεται στην μετατροπή του στιγμιοτύπου ${\pi }_1$ ενός προβλήματος ${\mathrm{\Pi }}_1$ σε ένα στιγμιότυπο ${\pi }_2$ του προβλήματος ${\mathrm{\Pi }}_2$ με τέτοιο τρόπο, ώστε η λύση στο ${\pi }_2$ να δίνει την λύση και στο ${\pi }_1$. Εμείς θα ασχοληθούμε με αναγωγές που υλοποιούνται σε έναν αιτιοκρατικό υπολογιστή σε πολυωνυμικό χρόνο. Αν το ${\pi }_1$ είναι ένα ΝΑΙ στιγμιότυπο του προβλήματος ${\mathrm{\Pi }}_1$,⁶⁶Θα μπορούσαμε να γράψουμε ${\pi }_1\in {\mathrm{\Pi }}_1$ αφού το ${\mathrm{\Pi }}_1$ είναι ένα σύνολο τέτοιων στιγμιοτύπων που έχουν τη συγκεκριμένη ιδιότητα. τότε η αναγωγή $R$ θα δώσει ένα ΝΑΙ στιγμιότυπο ${\pi }_2=R({\pi }_1)$ του προβλήματος ${\mathrm{\Pi }}_2$. Αντίστοιχα, αν το ${\pi }_1$ είναι ένα ΟΧΙ στιγμιότυπο του ${\mathrm{\Pi }}_1$, τότε και το ${\pi }_2$ θα είναι ένα ΟΧΙ στιγμιότυπο του ${\mathrm{\Pi }}_2$. Δηλαδή, χρησιμοποιώντας σημειογραφία συνόλων θα πρέπει να δειξουμε ότι η αναγωγή $R$ είναι πολυωνυμικού χρόνου και ότι ${\pi }_1\in {\mathrm{\Pi }}_1\iff {\pi }_2\in {\mathrm{\Pi }}_2$.

Σε αυτή την περίπτωση θα λέμε ότι το πρόβλημα ${\mathrm{\Pi }}_1$ ανάγεται στο πρόβλημα ${\mathrm{\Pi }}_2$ και συμβολίζουμε ως ${\mathrm{\Pi }}_1\le {\mathrm{\Pi }}_2$, το οποίο σημαίνει ότι μπορεί να χρησιμοποιηθεί η λύση του ${\mathrm{\Pi }}_2$, ώστε να λύσουμε το ${\mathrm{\Pi }}_1$. Το παρακάτω λήμμα δίνει μία πρώτη γεύση για την χρησιμότητα της αναγωγής.

Με βάση αυτό το λήμμα μπορούμε να επιλύουμε προβλήματα σε πολυωνυμικό χρόνο ανάγοντάς τα σε πολυωνυμικό χρόνο σε άλλα γνωστά προβλήματα που επίσης επιλύονται σε πολυωνυμικό χρόνο. Για παράδειγμα, το πρόβλημα της μεγαλύτερης μέγιστης αντιστοίχησης σε διμερές γράφημα ανάγεται στο πρόβλημα μέγιστης ροής σε ένα απλό γράφημα.

Η έννοια της αναγωγής μπορεί να χρησιμοποιηθεί και με έναν αντίστροφο τρόπο. Προσέξτε ότι όταν ανάγουμε το πρόβλημα ${\mathrm{\Pi }}_1$ στο πρόβλημα ${\mathrm{\Pi }}_2$ χρησιμοποιούμε το ${\mathrm{\Pi }}_2$ σαν διαδικασία για να λύσουμε το ${\mathrm{\Pi }}_1$. Με αυτή την έννοια και λαμβάνοντας υπ’όψιν ότι αναφερόμαστε σε προβλήματα τουλάχιστον πολυωνυμικής πολυπλοκότητας, μπορούμε να βγάλουμε το συμπέρασμα ότι το ${\mathrm{\Pi }}_2$ είναι ίσης ή και μεγαλύτερης δυσκολίας από το ${\mathrm{\Pi }}_1$. Για παράδειγμα, το ${\mathrm{\Pi }}_2$ θα μπορούσε να είναι πρόβλημα που λύνεται σε εκθετικό χρόνο, ενώ το ${\mathrm{\Pi }}_1$ να λύνεται σε πολυωνυμκό χρόνο αλλά ποτέ το αντίστροφο, αν υπήρχε αναγωγή πολυωνυμικού χρόνου από το ${\mathrm{\Pi }}_1$ στο ${\mathrm{\Pi }}_2$.

Αναφερόμενοι στην αντιθετοαντίστροφη μορφή του Λήμματος 10.1, αν το ${\mathrm{\Pi }}_1$ ανάγεται σε πολυωνυμικό χρόνο στο ${\mathrm{\Pi }}_2$ και το ${\mathrm{\Pi }}_1$ είναι εκθετικού χρόνου, τότε και το ${\mathrm{\Pi }}_2$ θα πρέπει να είναι εκθετικού χρόνου. Ακριβώς αυτή τη μορφή της αναγωγής χρησιμοποιούμε για να δείξουμε ότι πολλά προβλήματα της Θεωρίας Γράφων είναι δύσκολα ως προς τη πολυπλοκότητά τους προβλήματα.

Σε αυτό το κεφάλαιο θα αναφερθούμε σε κάποιες θεμελιώδεις κλάσεις πολυπλοκότητας που περιλαμβάνουν τις κλάσεις $𝒫$, $𝒩𝒫$ και την $𝒩𝒫𝒞$. Αν ο αναγνώστης επιθυμεί περισσότερη πληροφορία σε σχέση με τις κλάσεις πολυπλοκότητας, μπορεί να χρησιμοποιήσει σαν αναφορές τα βιβλία [8, 143].

Οι Garey και Johnson στο βιβλίο τους ”Computers and Intractability: a Guide to the Theory of $𝒩𝒫$-completeness” [52] (σελίδες 187-288), συγκέντρωσαν όλα τα μέχρι το 1979 γνωστά $𝒩𝒫$-πλήρη προβλήματα. Τα προβλήματα αυτά ομαδοποιήθηκαν στις εξής 12 κατηγορίες:

• •

  Θεωρία γράφων (65)

• •

  Σχεδιασμός δικτύων (51)

• •

  Σύνολα και διαμερισμοί (21)

• •

  Αποθήκευση και ανάκτηση (36)

• •

  Σειριοποίηση και δρομολόγηση (22)

• •

  Μαθηματικός προγραμματισμός (13)

• •

  Άλγεβρα και Θεωρία αριθμών (18)

• •

  Παίγνια και σπαζοκεφαλιές (15)

• •

  Λογική (19)

• •

  Αυτόματα και γλώσσες (21)

• •

  Βελτιστοποίηση προγραμμάτων (20)

• •

  Διάφορα (19)

Ο αριθμός στην παρένθεση δηλώνει τον αντίστοιχο αριθμό προβλημάτων. Έτσι, το σύνολο των καταγραμμένων $𝒩𝒫$-πλήρων προβλημάτων το 1979 ανέρχονταν στα 320 από πολλές περιοχές της Πληροφορικής. Ταυτόχρονα, υπήρχε και μία λίστα 12 ανοικτών προβλημάτων για τα οποία δεν είχε αποδειχθεί αν ανήκουν ή όχι στην κατηγορία των $𝒩𝒫$-πλήρων προβλημάτων. Στην επανεκτύπωση του βιβλίου το 1991 υπάρχει ένα νέο σχόλιο των συγγραφέων, όπου καταγράφεται ότι έχουν επιλυθεί τα 8 από τα 12 ανοικτά προβλήματα της έκδοσης του 1979. Από αυτά τα 8 προβλήματα, για 4 αποδείχθηκε ότι ανήκουν στην κλάση $𝒫$, ενώ για άλλα $4$ αποδείχθηκε ότι ανήκουν στην κλάση $𝒩𝒫$.

Από τότε, όμως, η θεωρία της $𝒩𝒫$-πληρότητας έχει εφαρμοσθεί και σε άλλες περιοχές με αποτέλεσμα πολλά προβλήματα που δεν προκύπτουν μέσα από την Επιστήμη της Πληροφορικής να έχουν χαρακτηρισθεί ως $𝒩𝒫$-πλήρη. Αναφέρουμε στη συνέχεια ενδεικτικά μερικές περιπτώσεις:

• •

  Βιολογία: πως διπλώνεται μία πρωτεΐνη στον $3$-διάστατο χώρο

• •

  Θεωρία Παιγνίων: εύρεση ισορροπιών Nash που μεγιστοποιούν την ωφέλεια του συνόλου

• •

  Μηχανική Περιβάλλοντος: βέλτιστη τοποθέτηση αισθητήρων μόλυνσης

• •

  Στατιστική Φυσική: εύρεση συνάρτησης διαμέρισης για το $3$-διάστατο Ising μοντέλο

• •

  Πολιτική Επιστήμη: Υπολογισμός του δείκτη Shapley-Shubik ισχύος σε ψηφοφορία

• •

  Pop κουλτούρα: υπολογισμός λύσης από μία συγκεκριμένη θέση για το παιχνίδι Ναρκαλιευτής

Σε αυτό το κεφάλαιο συζητήσαμε αρκετά συνοπτικά βασικά στοιχεία της πολυπλοκότητας. Γενικά, η θεωρία γράφων είναι μία πλούσια πηγή $𝒩𝒫$-πλήρων προβλημάτων λόγω και της εκτεταμένης χρήσης των γράφων ως εργαλείο μοντελοποίησης προβλημάτων. Το βιβλίο των Garey και Johnson [52] παραμένει ακόμα η βασική αναφορά για την θεωρία της $𝒩𝒫$-πληρότητας και τα περισσότερα προβλήματα που αναφέρονται στην Ενότητα 10.4 είναι από αυτό το βιβλίο. Από το 1979, όμως, η περιοχή έχει προχωρήσει πολύ. Στο βιβλίο του Παπαδημητρίου [143] υπάρχει μία πιο σύγχρονη αντιμετώπιση του θέματος, ενώ αναλύονται και άλλες υποπεριοχές της Πολυπλοκότητας. Για μία όμως σύγχρονη αντιμετώπιση του θέματος όπου πολλά θέματα στην Πολυπλοκότητα που έχουν αναπτυχθεί την δεκαετία (2000-2009) αναφέρονται αναλυτικά θα πρέπει κάποιος να διαβάσει το βιβλίο των Arora και Barak [8].

Για ένα από τα πιο γνωστά $𝒩𝒫$-πλήρη προβλήματα, αυτό του TSP, ο ενδιαφερόμενος αναγνώστης μπορεί να βρει μία αναλυτική παρουσίαση αλγορίθμων και αποτελεσμάτων που αφορούν τη δυσκολία του προβλήματος στα βιβλία [70, 84].

1. 1.

   Από τη λίστα των $𝒩𝒫$-πλήρων προβλημάτων της Ενότητας 10.4 να επιλεγεί ένα πρόβλημα και να αποδειχθεί ότι κάποιο άλλο από τη λίστα είναι επίσης $𝒩𝒫$-πλήρες. Προσοχή, η επιλογή του ζεύγους πρέπει να γίνει με τρόπο, ώστε τα προβλήματα να έχουν κάποια συγγένεια και η αναγωγή να είναι εύκολη.

2. 2.

   Να αποδειχθεί ότι αν ένα $𝒩𝒫$-πλήρες πρόβλημα μπορεί να λυθεί σε πολυωνυμικό χρόνο, τότε $𝒫=𝒩𝒫$.

3. 3.

   Έστω ο τύπος γραφήματος όπου οι κορυφές είναι σημεία ενός πλέγματος σε ένα $n$-διάστατο κύβο, όπου κάθε ακμή έχει $m$ κορυφές. Αυτό σημαίνει ότι οι κορυφές μπορούν να αναπαρασταθούν από διανύσματα $(i_1,i_2,\mathrm{\dots },i_n)$ όπου $i_j\in [1\mathrm{\dots }m],i_j\in \mathbb{N}$. Υπάρχει μία ακμή μεταξύ δύο κόμβων μόνο αν διαφέρουν τα διανύσματά τους σε μία διάσταση ακριβώς. Για παράδειγμα, η περίπτωση $n=2$ και $m=2$ αντιστοιχεί σε ένα τετράγωνο, ενώ η περίπτωση $n=m=3$ αντιστοιχεί σε κύβο. Μερικά από αυτά τα γραφήματα έχουν Hamiltonian κύκλωμα, ενώ κάποια άλλα δεν έχουν. Για παράδειγμα, το τετράγωνο και ο κύβος έχουν Hamiltonian κύκλωμα, αλλά το γράφημα για $n=2$ και $m=3$ δεν έχει.

   1. (a)

      Να αποδείχθεί ότι το γράφημα για $n=2$ και $m=3$ δεν έχει Hamiltonian κύκλωμα. Υπόδειξη: Σκεφτείτε τι γίνεται αν ένα υποθετικό Hamiltonian κύκλωμα περάσει από τον κεντρικό κόμβο. Από πού έρχεται και που μπορεί να μεταβεί χωρίς να αποκόψει κάποιο κομμάτι από το Hamiltonian κύκλωμα;

   2. (b)

      Για ποιες τιμές του $n$ και $m$ υπάρχει Hamiltonian κύκλωμα; Το πρόβλημα ύπαρξης Hamiltonian κυκλώματος σε αυτά τα γραφήματα παραμένει $𝒩𝒫$-πλήρες;

4. 4.

   Ένας γράφος δεν χρειάζεται να είναι εξαιρετικά μεγάλος πριν οι ερωτήσεις σχετικά με $𝒩𝒫$-πλήρη προβλήματα γίνουν αρκετά δυσκολες για να λυθούν με το χέρι. Έστω το γράφημα του Σχήματος 10.2.

   1. (a)

      Έχει ο γράφος Hamiltonian κύκλωμα;

   2. (b)

      Ποιό είναι το μέγιστο ανεξάρτητο σύνολο;

   3. (c)

      Ποιό είναι το ελάχιστο σύνολο κάλυψης;

   4. (d)

      Ποιο είναι το ελάχιστο συνολο κάλυψης ακμών;

   5. (e)

      Είναι ο γράφος 2-χρωματίσιμος;

   

5. 5.

   Να αποδειχθεί ότι το πρόβλημα της διαπίστωσης, αν ένας γράφος είναι Hamiltonian, ανήκει στην κλάση $𝒩𝒫$.

6. 6.

   Να αποδειχθεί ότι το πρόβλημα της διαπίστωσης, αν ένας γράφος μπορεί να χρωματισθεί με 3 μόνο χρώματα, είναι $𝒩𝒫$-πλήρες.