Το μεγαλύτερο πρόβλημα της πληροφορικής: P εναντίον NP

Υπάρχουν επτά μαθηματικά προβλήματα που θεωρήθηκαν τόσο δύσκολα και ενδιαφέροντα, ώστε το Ινστιτούτο Μαθηματικών Clay τα ονόμασε προβλήματα της χιλιετίας και όποιος λύσει οποιοδήποτε από αυτά παίρνει έπαθλο ένα εκατομμύριο δολάρια. Ένα από τα προβλήματα αγγίζει και την πληροφορική και λέγεται πρόβλημα P εναντίον NP. Ας εξηγήσουμε περί τίνος πρόκειται.

Λοιπόν. Ας μην κοροϊδευόμαστε ότι θα είναι εύκολο να εξηγηθεί. Άλλωστε είναι πρόβλημα της χιλιετίας. Πήγαινε λοιπόν να φτιάξεις ένα καλό πράσινο τσάι 🍵 και ας ξεκινήσουμε. Πρώτα θα δούμε τέσσερα διαφορετικά προβλήματα από τον κόσμο της πληροφορικής και των αλγορίθμων. Θα αναλύσουμε τα προβλήματα και θα δούμε τι σχέση έχουν με τα γράμματα P και NP.

Πρόβλημα αρ. 1: Εύρεση του μικρότερου αριθμού

Το P εναντίον NP αφορά τους αλγορίθμους και την πολυπλοκότητά τους. Φαντάσου ότι σου ρίχνω μπροστά εκατό χαρτάκια, στο καθένα είναι γραμμένος ένας αριθμός, και σου ζητώ να βρεις το χαρτάκι με τον μικρότερο αριθμό. Πόσο θα σου πάρει;

Μισό λεπτό; Δύο λεπτά;

Αυτές είναι μονάδες χρόνου που δεν μας απασχολούν και τόσο στη θεωρητική πληροφορική. Αυτό που μας ενδιαφέρει περισσότερο είναι ο αριθμός των πράξεων. Θα μπορούσαμε λοιπόν να ρωτήσουμε λίγο διαφορετικά: πόσα χαρτάκια πρέπει να ελέγξω για να είμαι βέβαιος ότι βρήκα τον μικρότερο αριθμό; Η απάντηση είναι ότι πρέπει να ελέγξω όλα τα χαρτάκια – γιατί ο μικρότερος αριθμός μπορεί να είναι στο τελευταίο χαρτάκι. Όταν σου ρίξω εκατό χαρτάκια, πρέπει να ελέγξεις εκατό χαρτάκια. Όταν σου ρίξω χίλια, πρέπει να ελέγξεις χίλια. Γενικά, όταν σου ρίξω n χαρτάκια, πρέπει να ελέγξεις n χαρτάκια.

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

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

Υπάρχουν αλγόριθμοι για τους οποίους είναι ευκολότερο να ελέγξουμε το αποτέλεσμα παρά να το βρούμε;

Πρόβλημα αρ. 2: Γινόμενο ζεύγους

Φαντάσου ότι σου ρίχνω δύο ισομεγέθεις στοίβες από χαρτάκια, σε κάθε χαρτάκι υπάρχει πάλι ένας αριθμός. Και τώρα θα ήθελα να βρεις έναν αριθμό από τη στοίβα A και έναν αριθμό από τη στοίβα B ώστε το γινόμενό τους να δίνει τον αριθμό 918. Για παράδειγμα, ας έχουμε τις εξής στοίβες αριθμών:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

Πώς μπορούμε να βρούμε ένα ζεύγος αριθμών ώστε το γινόμενό τους να ισούται με 918; Λοιπόν, μπορούμε απλώς να δοκιμάσουμε όλες τις δυνατότητες. Πόσες θα είναι; Αρκετές, θα είναι 25. Ξεκινάμε πολλαπλασιάζοντας τον πρώτο αριθμό της στοίβας A, δηλαδή το 49, με κάθε αριθμό της στοίβας B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Κανένα ζεύγος αριθμών δεν οδηγεί στο 918. Δοκιμάζουμε λοιπόν το ίδιο με τους υπόλοιπους αριθμούς της στοίβας A, δηλαδή άλλα πέντε ζεύγη για τον αριθμό 11, άλλα πέντε ζεύγη για τον αριθμό 32, άλλα πέντε ζεύγη για το 54 και τα τελευταία πέντε ζεύγη για το 15. Συνολικά μπορούμε να δοκιμάσουμε 25 ζεύγη αριθμών. Τελικά βρίσκουμε ότι 54 · 17 = 918.

Ποια είναι η πολυπλοκότητα αυτού του αλγορίθμου; Θα μας ενδιαφέρει πόσα ζεύγη αριθμών χρειάστηκε να πολλαπλασιάσουμε. Και οι δύο στοίβες περιείχαν πέντε χαρτάκια και εμείς έπρεπε να δοκιμάσουμε καθέναν από τους πέντε αριθμούς της πρώτης στοίβας με καθέναν από τους πέντε αριθμούς της δεύτερης. Συνολικά δοκιμάσαμε 5 · 5 = 25 συνδυασμούς. Αν σου ρίξω δύο στοίβες με 10 χαρτάκια, θα έπρεπε να δοκιμάσεις 10 · 10 = 100 συνδυασμούς. Γενικεύοντας, αν σου ρίξω δύο στοίβες με n χαρτάκια, πρέπει να δοκιμάσεις n · n = n² συνδυασμούς.

Λέμε ότι αυτός ο αλγόριθμός μας έχει πολυπλοκότητα n², τετραγωνική πολυπλοκότητα, επειδή την περιγράφει η τετραγωνική συνάρτηση.

Πόσο δύσκολο όμως θα είναι να ελέγξουμε το αποτέλεσμα; Αν μου απαντήσεις ότι το 54 και το 17 είναι αριθμοί των οποίων το γινόμενο δίνει 918, δεν χρειάζεται πια να περάσω από όλα τα ζεύγη αριθμών των δύο στοιβών όπως έπρεπε να κάνεις εσύ. Μου αρκεί να πολλαπλασιάσω αυτό το ένα ζεύγος 54 · 17 και θα ξέρω αν έχεις δίκιο ή όχι. Ενώ λοιπόν για την επίλυση αυτού του προβλήματος χρειάζεται να υπολογίσουμε μέχρι και n² γινόμενα, για την επαλήθευση αρκεί να υπολογίσουμε μόνο ένα γινόμενο. Η επαλήθευση έχει λοιπόν σταθερή πολυπλοκότητα 1.

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

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

Πρόβλημα αρ. 3: Άθροισμα υποσυνόλου

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

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Διάλεξε από αυτούς τους αριθμούς οποιαδήποτε ομάδα αριθμών με άθροισμα 0. Για παράδειγμα οι αριθμοί

$24 + 48 - 69 + 1$

δίνουν άθροισμα 4 και άρα δεν είναι σωστή απάντηση. Σωστή απάντηση είναι η ομάδα αριθμών… και ξέρεις τι; Δοκίμασε να τη βρεις μόνος σου ως δουλειά για το σπίτι 😉. Υπάρχει μία μόνο ομάδα αριθμών με άθροισμα 0. Τουλάχιστον θα δοκιμάσεις πόσο δύσκολο είναι αυτό το πρόβλημα.

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

Πώς μπορούμε λοιπόν να βρούμε μια ομάδα αριθμών με άθροισμα 0; Λοιπόν, πρέπει απλώς να δοκιμάσουμε όλους τους πιθανούς συνδυασμούς αριθμών. Πρέπει να δοκιμάσουμε όλα τα ζεύγη αριθμών, όλες τις τριάδες, τετράδες, πεντάδες κ.ο.κ. και για κάθε ομάδα πρέπει να ελέγξουμε αν το άθροισμά της δίνει μηδέν. Πόσοι τέτοιοι συνδυασμοί υπάρχουν;

Ας το δείξουμε σε ένα μικρότερο σύνολο αριθμών. Πόσες διαφορετικές ομάδες αριθμών, δηλαδή υποσύνολα, μπορώ να φτιάξω από την τριάδα αριθμών B = {5, 7, 9}; Είναι συνολικά οκτώ:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Πρόσεξε ότι συμπεριλάβαμε και το κενό υποσύνολο B₁. Δεν είναι τώρα και πολύ χρήσιμο, αλλά για την τάξη το αφήσαμε. Για να απλοποιήσουμε τον υπολογισμό, αντιστοιχίζουμε σε κάθε υποσύνολο ένα δυαδικό διάνυσμα. Το δυαδικό διάνυσμα είναι απλώς μια ακολουθία μηδενικών και μονάδων, για παράδειγμα 00101010. Εμείς θα δουλεύουμε με δυαδικά διανύσματα μήκους τρία. Το διάνυσμα αντιστοιχίζεται έτσι: το 101 το αντιστοιχίζουμε στο υποσύνολο που περιέχει «τον πρώτο και τον τρίτο αριθμό του αρχικού συνόλου, αλλά όχι τον δεύτερο», δηλαδή στο σύνολο {5, 9}. Το διάνυσμα 110 το αντιστοιχίζουμε στο υποσύνολο που περιέχει «τον πρώτο και τον δεύτερο αριθμό του αρχικού συνόλου, αλλά όχι τον τρίτο», δηλαδή στο σύνολο {5, 7} κ.ο.κ.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

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

Δυαδικά διανύσματα μήκους ένα υπάρχουν δύο: το 0 και το 1.

Δυαδικά διανύσματα μήκους δύο παίρνουμε αν πάρουμε όλα τα δυαδικά διανύσματα μήκους ένα και στο τέλος κάθε διανύσματος προσθέσουμε 0: παίρνουμε τα διανύσματα 00 και 10. Πάλι παίρνουμε όλα τα διανύσματα μήκους 1 και προσθέτουμε στο τέλος 1: 01 και 11. Έτσι πήραμε όλα τα διανύσματα μήκους 2: 00, 01, 10 και 11.

Δυαδικά διανύσματα μήκους τρία παίρνουμε αν πάρουμε όλα τα δυαδικά διανύσματα μήκους δύο και στο τέλος προσθέσουμε μηδέν: 000, 010, 100 και 110 και μονάδα: 001, 011, 101 και 111.

Και ούτω καθεξής για κάθε επόμενο μήκος. Βλέπουμε ότι όταν αυξήσουμε το μήκος του δυαδικού διανύσματος κατά ένα, ο αριθμός των διαφορετικών δυαδικών διανυσμάτων διπλασιάζεται. Για μήκος διανύσματος τέσσερα θα παίρναμε λοιπόν συνολικά 2 · 2 · 2 · 2, δηλαδή 16, διαφορετικούς συνδυασμούς.

Γενικά μπορούμε να συμπεράνουμε ότι αν έχουμε ένα σύνολο M που περιέχει n στοιχεία, τότε ο αριθμός όλων των υποσυνόλων αυτού του συνόλου M ισούται με τον αριθμό όλων των διαφορετικών δυαδικών διανυσμάτων μήκους n και αυτός ισούται με

$\underset{n φορές}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ ή n² – δεν είναι το ίδιο; Ένα και το αυτό 🤷‍♂

Υπάρχουν λοιπόν 2ⁿ διαφορετικά υποσύνολα που μπορούμε να φτιάξουμε από ένα σύνολο με n αριθμούς. Στην περίπτωσή μας έχουμε n = 12 αριθμούς και πρέπει άρα να ελέγξουμε 2¹² διαφορετικούς συνδυασμούς, δηλαδή 4096 συνδυασμούς. Λέμε ότι αυτό το πρόβλημα έχει πολυπλοκότητα 2ⁿ, εκθετική πολυπλοκότητα, επειδή το περιγράφει η εκθετική συνάρτηση.

Πρόσεξε ότι το προηγούμενο πρόβλημα είχε πολυπλοκότητα n², ενώ αυτό έχει πολυπλοκότητα 2ⁿ. Μοιάζει πολύ, έτσι; Όμως υπάρχει μεγάλη διαφορά ανάμεσα στο να έχουμε σταθερό εκθέτη και στο να έχουμε εκεί τη μεταβλητή n. Πρόσεξε ότι όταν n = 4, παίρνουμε

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Πολύ καλά, προς το παρόν μας βγαίνουν ίσα. Τι γίνεται όταν n = 10;

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Ωπ, η εκθετική συνάρτηση εκτοξεύτηκε και είναι ξαφνικά περίπου δέκα φορές μεγαλύτερη από την τετραγωνική. Τι παίρνουμε για n = 20;

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1.048 .576 \end{array}$

Η εκθετική πολυπλοκότητα έχει για n = 20 περίπου 2600 φορές μεγαλύτερη τιμή από την τετραγωνική πολυπλοκότητα. Βλέπουμε λοιπόν ότι η εκθετική συνάρτηση αυξάνεται πολύ πιο γρήγορα από την τετραγωνική συνάρτηση. Θυμήσου το όταν μας χτυπήσει ξανά καμία πανδημία που θα εξαπλώνεται στον πληθυσμό με εκθετικό ρυθμό.

Αν σου ρίξω λοιπόν είκοσι χαρτάκια, θα έπρεπε να ελέγξεις 1.048.576 συνδυασμούς. Είναι αρκετά πολλοί.

Πώς επαληθεύουμε την ορθότητα του αποτελέσματος;

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

Βλέπουμε πάλι ότι ο έλεγχος του αποτελέσματος είναι τάξεις μεγέθους ευκολότερος από την εύρεσή του.

Πρόβλημα αρ. 4: Το πρόβλημα του περιοδεύοντος πωλητή

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

Πώς μπορούμε να βρούμε αυτή τη συντομότερη διαδρομή; Δοκιμάζουμε όλες τις δυνατότητες.

Μπορούμε να το απλοποιήσουμε. Ας φανταστούμε ότι ανάμεσα σε κάθε δύο πόλεις υπάρχει ακριβώς μία συντομότερη διαδρομή. Πώς μπορούμε να βρούμε τη συντομότερη διαδρομή ανάμεσα σε όλες τις πόλεις; Έχουμε 14 πόλεις. Έχουμε λοιπόν 14 δυνατότητες για το πού να ξεκινήσουμε. Ας πούμε ότι ξεκινήσαμε από τη Θεσσαλονίκη!!! Πού μπορούμε να πάμε από τη Θεσσαλονίκη; Θεωρητικά μπορούμε να πάμε σε οποιαδήποτε άλλη πόλη. Μπορούμε λοιπόν να διαλέξουμε από τις 13 εναπομείνασες πόλεις.

Ήδη τώρα μπορούμε να υπολογίσουμε ότι έχουμε συνολικά 14 · 13 δυνατότητες για να επισκεφθούμε τις δύο πρώτες πόλεις – έχουμε 14 δυνατότητες για το πού να ξεκινήσουμε και μετά έχουμε να διαλέξουμε από τις 13 εναπομείνασες πόλεις.

Όταν φτάσουμε στη δεύτερη πόλη, πρέπει να συνεχίσουμε. Σε δύο πόλεις έχουμε ήδη πάει, άρα μπορούμε να ταξιδέψουμε σε μία από τις 12 εναπομείνασες πόλεις. Έχουμε έτσι συνολικά 14 · 13 · 12 δυνατότητες για να επισκεφθούμε τις τρεις πρώτες πόλεις.

Όταν επισκεφθούμε την τρίτη πόλη, πρέπει να διαλέξουμε μία από τις 11 εναπομείνασες πόλεις, μετά μία από τις 10 εναπομείνασες πόλεις κ.ο.κ.

Όταν επισκεφθούμε όλες, θα διαπιστώσουμε ότι είχαμε να διαλέξουμε συνολικά ανάμεσα σε

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

δυνατότητες. Αυτό μπορεί να σου θυμίζει το παραγοντικό, που το συμβολίζουμε με θαυμαστικό. Μπορούμε λοιπόν να πούμε ότι αυτό το γινόμενο ισούται με 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

και άρα υπάρχουν 14! διαδρομές που περνούν από όλες τις μεγάλες πόλεις της Ελλάδας. Είναι πολλές; Αρκετές, γιατί

$14! = 87.178 .291 .200 .$

Γενικά, αν ψάχναμε τη συντομότερη διαδρομή ανάμεσα σε n πόλεις, θα έπρεπε να δοκιμάσουμε n! διαφορετικές διαδρομές. Η πολυπλοκότητα αυτής της λύσης είναι λοιπόν n!.

Πώς θα επαληθεύαμε ότι βρήκαμε το σωστό αποτέλεσμα; Αν μου έλεγες ότι η συντομότερη διαδρομή είναι από την Πάτρα στη Θεσσαλονίκη, μετά στη Λάρισα κ.ο.κ., πώς μπορώ να επαληθεύσω ότι λες αλήθεια; Λοιπόν, δύσκολα 🤷‍♂. Γιατί όταν κοιτάζω αυτή τη διαδρομή, δεν έχω τρόπο να ελέγξω εύκολα αν είναι πράγματι η συντομότερη. Πρέπει στην ουσία να κάνω ξανά ολόκληρο τον υπολογισμό. Η πολυπλοκότητα της επαλήθευσης του αποτελέσματος είναι λοιπόν επίσης n!.

Οι κλάσεις P και NP

Παρουσιάσαμε τέσσερα προβλήματα και τους αλγορίθμους που τα λύνουν και αναλύσαμε πόσο δύσκολο είναι να βρούμε τη λύση και πόσο δύσκολο είναι να ελέγξουμε αυτή τη λύση. Μπορούμε να τα συνοψίσουμε σε αυτόν τον πίνακα:

Πρόβλημα	Πολυπλοκότητα λύσης	Πολυπλοκότητα επαλήθευσης
Μικρότερος αριθμός	n	n
Γινόμενο ζεύγους	n²	1
Άθροισμα υποσυνόλου	2ⁿ	n
Περιοδεύων πωλητής	n!	n!

Τώρα θα χωρίσουμε τα προβλήματά μας σε δύο ομάδες. Την πρώτη ομάδα θα αποτελούν τα προβλήματα που είναι εύκολα στην επίλυση. Είναι τα προβλήματα που μπορούν να λυθούν με πολυπλοκότητα n ή n² ή n³ ή n⁴ κ.ο.κ. Επειδή παραστάσεις όπως το n² τις λέμε πολυώνυμα, αυτή την κλάση προβλημάτων τη συμβολίζουμε με το γράμμα P. Λέμε λοιπόν ότι η κλάση P περιέχει τα προβλήματα που μπορούν να λυθούν σε πολυωνυμικό χρόνο (= έχουν πολυπλοκότητα, ας πούμε, n² ή n⁷). Γενικά είναι προβλήματα που μπορούν να λυθούν λίγο πολύ εύκολα.

Στην κλάση P ανήκει έτσι το πρόβλημα αρ. 1, η εύρεση του μικρότερου αριθμού, επειδή έχει πολυπλοκότητα λύσης n, και ανήκει και το πρόβλημα αρ. 2, το γινόμενο ζεύγους, επειδή η πολυπλοκότητα λύσης του είναι n², που είναι και τα δύο πολυώνυμα.

Η δεύτερη κλάση είναι η κλάση NP. Αυτή περιέχει τα προβλήματα που μπορούν να επαληθευτούν σε πολυωνυμικό χρόνο. Στην κλάση NP ανήκουν έτσι όλα τα προβλήματα, εκτός από το τελευταίο. Το πρόβλημα του περιοδεύοντος πωλητή δεν μπορούμε να το επαληθεύσουμε σε πολυωνυμικό χρόνο. Τα προηγούμενα τρία προβλήματα μπορούν να επαληθευτούν σε πολυωνυμικό χρόνο.

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

Είναι προφανές ότι η κλάση P είναι υποσύνολο της κλάσης NP. Δηλαδή κάθε πρόβλημα που ανήκει στην κλάση P ανήκει ταυτόχρονα και στην κλάση NP. Βγάζει νόημα – αν μπορούμε να λύσουμε ένα πρόβλημα σε πολυωνυμικό χρόνο, μπορούμε και να επαληθεύσουμε το αποτέλεσμα σε πολυωνυμικό χρόνο.

Το πρόβλημα P εναντίον NP

Ισχύει όμως και το αντίστροφο; Κάθε πρόβλημα της κλάσης NP ανήκει ταυτόχρονα και στην κλάση P; Δηλαδή, αν υπάρχει τρόπος να επαληθεύσουμε το αποτέλεσμα ενός προβλήματος σε πολυωνυμικό χρόνο, υπάρχει και αλγόριθμος που θα έλυνε το πρόβλημα σε πολυωνυμικό χρόνο;

Για παράδειγμα, ξέρουμε ότι μπορούμε να επαληθεύσουμε το αποτέλεσμα του προβλήματος αρ. 3, του αθροίσματος υποσυνόλου, σε πολυωνυμικό χρόνο. Αλλά για να το λύσουμε χρησιμοποιήσαμε έναν αλγόριθμο που δεν είναι πολυωνυμικός, ο αλγόριθμος που χρησιμοποιήσαμε έχει εκθετική πολυπλοκότητα 2ⁿ. Ξέρουμε όμως με βεβαιότητα ότι για αυτό το πρόβλημα δεν υπάρχει κανένας αλγόριθμος με πολυωνυμική πολυπλοκότητα;

Δεν ξέρουμε!

Θα μπορούσε κάλλιστα να συμβαίνει ότι για κάθε πρόβλημα που μπορεί να επαληθευτεί σε πολυωνυμικό χρόνο υπάρχει αλγόριθμος που λύνει αυτό το πρόβλημα σε πολυωνυμικό χρόνο. Εμείς δεν το ξέρουμε. Δεν μπορούμε να αποδείξουμε την ύπαρξη ενός τέτοιου αλγορίθμου, αλλά δεν μπορούμε ούτε να διαψεύσουμε την ύπαρξή του.

Αν για κάθε πρόβλημα της κλάσης NP υπήρχε αλγόριθμος που το λύνει σε πολυωνυμικό χρόνο, αυτό θα σήμαινε ότι η κλάση NP θα ήταν στην ουσία ίση με την κλάση P. Όλα τα προβλήματα της κλάσης P θα ήταν στην κλάση NP και όλα τα προβλήματα της κλάσης NP θα ήταν στην κλάση P – οι δύο κλάσεις θα ήταν ίσες, ταυτόσημες.

Το πρόβλημα P εναντίον NP είναι λοιπόν το ερώτημα αν η κλάση P είναι ταυτόσημη με την κλάση NP ή αν πρόκειται για δύο διαφορετικές κλάσεις προβλημάτων.

Ή ισχύει λοιπόν P = NP, ή ισχύει P ≠ NP. Αυτό δεν το ξέρει κανείς και αν το ανακαλύψεις, σε περιμένει έπαθλο ένα εκατομμύριο δολάρια, αθάνατη δόξα και πιθανότατα και το βραβείο Turing, που είναι κάτι σαν το Νόμπελ των πληροφορικών.

Τι θα συνέβαινε αν P = NP;

Τι θα συνέβαινε αν ίσχυε ότι P = NP; Λοιπόν, δεν είναι εντελώς απλό να πούμε τι θα συνέβαινε. Θα ξέραμε ότι για όλα τα προβλήματα της κλάσης NP υπάρχει αλγόριθμος που τα λύνει σε πολυωνυμικό χρόνο. Για παράδειγμα, ότι για το πρόβλημά μας αρ. 3, το άθροισμα υποσυνόλου, υπάρχει αλγόριθμος που το λύνει σε πολυωνυμικό χρόνο. Αυτό όμως έχει τρία προβλήματα:

Το ότι θα ξέραμε ότι υπάρχει ένας τέτοιος αλγόριθμος δεν σημαίνει ότι μπορούμε να τον βρούμε. Απλώς θα ξέραμε ότι ναι, υπάρχει αλγόριθμος που λύνει το πρόβλημα σε πολυωνυμικό χρόνο, αλλά ίσως δεν θα μπορούσαμε να τον κατασκευάσουμε για άλλα εκατό χρόνια. Είναι κάτι παρόμοιο με το ότι η γενική θεωρία της σχετικότητας προέβλεψε την ύπαρξη των μαύρων τρυπών, αλλά παρ' όλα αυτά χρειάστηκαν αρκετές ακόμη δεκαετίες μέχρι να καταφέρουμε να τραβήξουμε την πρώτη «φωτογραφία» μιας μαύρης τρύπας.
Το ότι υπάρχει αλγόριθμος που δουλεύει σε πολυωνυμικό χρόνο δυστυχώς δεν σημαίνει ακόμη ότι είναι γρήγορος. Θα μπορούσαμε να βρούμε έναν αλγόριθμο που έχει πολυπλοκότητα n¹⁰⁰. Γιατί και η παράσταση n¹⁰⁰ είναι πολυώνυμο. Αν συγκρίνουμε τις πολυπλοκότητες 2ⁿ και n¹⁰⁰, θα διαπιστώσουμε ότι όσο το n είναι σχετικά μικρό, ο αλγόριθμος με πολυπλοκότητα 2ⁿ χρειάζεται ακόμη λιγότερες πράξεις. Για παράδειγμα, για n = 20 ισχύει ότι 2²⁰ = 1.048.576, ενώ η παράσταση 20¹⁰⁰ οδηγεί σε έναν αριθμό που έχει περίπου 130 ψηφία, δηλαδή έναν αριθμό που είναι κατά 120 τάξεις μεγέθους μεγαλύτερος από το 1.048.576. Ο πολυωνυμικός αλγόριθμός μας θα ήταν έτσι στην πράξη πιο αργός από τον εκθετικό. Τουλάχιστον όσο το n είναι σχετικά μικρό.
Αν παρ' όλα αυτά καταφέρναμε να βρούμε έναν γρήγορο αλγόριθμο που δουλεύει σε πολυωνυμικό χρόνο, θα μπορούσαμε να λύνουμε πολλά προβλήματα πιο γρήγορα και με μεγαλύτερη ακρίβεια. Αυτό είναι βέβαια θετικό νέο, αλλά έχει και τα αρνητικά του. Υπάρχει ένας κλάδος που βασίζεται στο ότι ορισμένα προβλήματα είναι δύσκολο να λυθούν και αυτός είναι η κρυπτογραφία – η κρυπτογράφηση. Θα μπορούσε έτσι να συμβεί να γίνει τάξεις μεγέθους ευκολότερο να σπάσουν οι σημερινοί κρυπτογραφικοί αλγόριθμοι.

Διάλειμμα: επειδή διάβασες μέχρι εδώ, για ανταμοιβή θα σου αποκαλύψω ότι η λύση του προβλήματος αρ. 3 είναι 24 + 1 − 60 + 16 − 83 + 48 + 54.

Τι θα συνέβαινε αν P ≠ NP;

Αν ίσχυε ότι οι κλάσεις προβλημάτων P και NP είναι διαφορετικές, τότε δεν θα άλλαζαν και πολλά, γιατί αυτό είναι λίγο πολύ το status quo. Εμείς προς το παρόν δεν έχουμε κανέναν αλγόριθμο που να λύνει κάποιο δύσκολο πρόβλημα της NP σε πολυωνυμικό χρόνο και αν κάποιος αποδείκνυε ότι P ≠ NP, τότε απλώς θα έμενε έτσι για πάντα. Πολύ μεγαλύτερη αίσθηση θα έκανε η απόδειξη ότι P = NP.

Αναφορές στη λαϊκή κουλτούρα

Σε ένα επεισόδιο των Simpsons βλέπουμε τον Homer να μπαίνει σε μια εναλλακτική πραγματικότητα, στην οποία του αποκαλύπτεται ότι P = NP. Μπορείς να το δεις στο youtube.com.
Αντίθετα, στο Futurama βλέπουμε ότι έχουν στην αποθήκη δύο φακέλους, έναν με το όνομα P και έναν με το όνομα NP. Μπορείς να το δεις στο youtube.com.
Το δεύτερο επεισόδιο της δεύτερης σεζόν της σειράς Elementary με τίτλο «Solve for X» αφορούσε τη δολοφονία ενός μαθηματικού που πιθανώς είχε λύσει το πρόβλημα P εναντίον NP.

« Προηγούμενο: Πόσο κάνει 1 + 2 + 5 · 0;

Επόμενο: Η μέθοδος Τράχτενμπεργκ για γρήγορη πρόσθεση »