Είναι το P ίσο με το NP? Ιδού η απορία!

Επειδή πολύ μιζέρια έχει πέσει τελευταία είπα να ασχοληθώ με κάτι που δεν αφορά την πολιτική και την οικονομία σε αυτό το post. Θα προσπαθήσω να εξηγήσω όσο πιο απλά μπορώ ένα πρόβλημα της θεωρητικής επιστήμης των υπολογιστών συγκεκριμένα το ερώτημα αν P=NP. Το πρόβλημα αυτό βρίσκεται στο σταυροδρόμι Επιστήμης Υπολογιστών και Μαθηματικών και είναι ένα από τα 7 προβλήματα τα οποία είναι γνωστά ως Millennium Prize Problems και μία σωστή λύση σε καθένα από αυτά αξίζει 1 εκατομύριο δολάρια.

Τι σκ@#@ είναι το P;

Το λοιπόν, έχουμε προβλήματα που θέλουμε να λύσουμε αλλά είμαστε και λίγο βιαστικοί και δεν θέλουμε η λύση να παίρνει πάρα πολύ χρόνο. Για παράδειγμα αν είχαμε μία εικόνα και θέλαμε να αλλάξουμε κάθε pixel από μπλε σε κόκκινο, θα επισκεπτόμασταν κάθε pixel και θα κάναμε την ερώτηση: “Φιλαράκο, μήπως είσαι μπλε;” Αν η απάντηση είναι καταφατική, του αλλάζουμε τα φώτα. Απλό έτσι;

Και τώρα μία σημαντική ερώτηση: Πόσα βήματα κάναμε; Αν είχαμε n pixels συνολικά κάναμε n βήματα, ή αν προτιμάτε να θεωρείτε την ερώτηση 1 βήμα και την αλλαγή χρώματος ένα δεύτερο, κάναμε το πολύ 2n βήματα. Δεν έχει και πολύ σημασία γιατί φοράμε το καπέλο του θεωρητικού της Επιστήμης των υπολογιστών και δεν μας πολυενδιαφέρουν τέτοιες λεπτομέρειες. Το σημαντικό είναι ότι κάναμε έναν αριθμό βημάτων ο οποίος είναι πολυωνυμικός ως προς το πλήθος των pixels.

Το πρόβλημα λοιπόν που περιγράψαμε παραπάνω λύνεται σε πολυωνυμικό χρόνο για οποιαδήποτε εικόνα και αν μας δώσουν να επεξεργαστούμε και άρα είναι στην κλάση των προβλημάτων που λύνονται σε πολυωνυμικό χρόνο (duh!) την οποία ονομάζουμε P.

Ένα άλλο πρόβλημα που ανήκει στην κλάση P (δηλαδή λύνεται σε πολυωνυμικό χρόνο) είναι η εύρεση του μέγιστου κοινού διαιρέτη δύο ακαιρέων. Συνήθως χρησιμοποιούμε τον αλγόριθμο του Ευκλείδη. Δεν έχει και πολύ μεγάλη σημασία για αυτή την κουβέντα να καταλάβετε πώς δουλεύει, μόνο ότι ο αριθμός των βημάτων που χρειάζονται για να βρούμε την απάντηση είναι πολυωνυμικός ως προς την είσοδο.

Τέλος ένα άλλο πρόβλημα που ανήκει το P, είναι το να αποφασίσουμε αν ένας θετικός ακέραιος αριθμός είναι πρώτος (θυμίζω ότι ένας θετικός ακέραιος είναι πρώτος αν διαιρείται μόνο με το 1 και τον εαυτό του). Και αν πείτε “σιγά την ανακάλυψη” θα σας ενημερώσω ότι α) το πρόβλημα αυτό είναι ιδιαιτέρως σημαντικό για την κρυπτογραφία και β) ότι αποδείξαμε ότι ανήκει στο P μόλις το 2002.

Καλά ως εδώ, υπάρχει τίποτα άλλο;

Η αλήθεια είναι ότι υπάρχουν και προβλήματα που δε λύνονται τόσο εύκολα. Για παράδειγμα αν ξέρατε ότι το password μου αποτελείται από 8 πεζούς λατινικούς χαρακτήρες, θα έπρεπε να δοκιμάσετε το πολύ 268 συνδυασμούς μέχρι να το βρείτε.

Αν μου πείτε “χα! πάλι πολυωνυμικό πλήθος βημάτων χρειάζεται να κάνω αφού το 268 είναι πολυώνυμο” θα σας πω “Πρόσεξε εδώ κοιμισμένε/κοιμισμένη! Αν το password ήταν 9 χαρακτήρων θα χρειαζόταν να δοκιμάσεις 269 συνδυασμούς”. Δηλαδή αν η είσοδος του προβλήματος έχει μήκος n χρειάζεστε 26n βήματα το οποίο δεν είναι πολυωνυμικό αλλά εκθετικό.

Κοιτάξτε όμως τι γίνεται: αν νομίζουμε ότι έχουμε τη σωστή λύση, χρειαζόμαστε πολυωνυμικό χρόνο για να ελέγξουμε αν πράγματι είναι σωστή. Είναι εύκολο αν έχεις ένα password να δεις αν δουλεύει. Και αυτός είναι ένας από τους τρόπους να ορίσει κανείς την κλάση προβλημάτων NP: Είναι όλα εκείνα τα προβλήματα τα οποία μπορούμε να ελέγξουμε αν έχουμε τη σωστή λύση σε πολυωνυμικό χρόνο.

Υπάρχουν άλλα προβλήματα στο NP; Ναι αμέ, και πολύ χρήσιμα μάλιστα! Για παράδειγμα ένα πρόβλημα που λέγεται “SAT”: Κάποιος σου δίνει μία λογική εξίσωση όπως η παρακάτω

(Α και Β ή όχι Γ) και (Α και όχι Δ) ή (Ε και όχι Β)

και σε ρωτάει αν υπάρχει έστω και ένας συνδυασμός των τιμών “αληθές” (α) και “ψευδές” (ψ) για τις μεταβλητές Α,Β,Γ,Δ και Ε η οποία να δίνει τιμή αλήθεια για όλη την εξίσωση. Για παράδειγμα αν δίναμε τις τιμές: Α=α, Β=α, Γ=ψ, Δ=ψ και Ε=α τότε έχουμε:

(α και α ή (όχι ψ)) και (α και (όχι ψ)) ή (α και (όχι α))

(α και α ή α) και (α και α) ή (α και ψ)

α και α ή ψ

α

Αν τα παραπάνω σας φαίνονται λίγο μαγικά μπορείτε να δείτε και εδώ. Το σημαντικό είναι ότι αν έχουμε τις τιμές για τις μεταβλητές μπορούμε πολύ εύκολα (σε πολυωνυμικό χρόνο) να ελέγξουμε αν ικανοποιεί την εξίσωση.

Γιατί είναι χρήσιμο αυτό το πρόβλημα; Μία εφαρμογή είναι στη σχεδίαση ψηφιακών κυκλωμάτων. Ένα ψηφιακό κύκλωμα δουλεύει ακριβώς όπως η παραπάνω εξίσωση, όπου η τιμή “α” αντιπροσωπεύεται από το 1 και η τιμή “ψ” από το 0 (δυαδικό σύστημα ρε κουφάλες ;)). Θα θέλαμε να ξέρουμε αν υπάρχουν τιμές των εισόδων για τις οποίες ένα κύκλωμα βγάζει ως έξοδο 1. Γιατί αν δεν υπάρχουν τότε το κύκλωμα βγάζει πάντα 0 και μπορεί να αντικατασταθεί από ένα και μόνο καλώδιο.

Άλλο χρήσιμο πρόβλημα είναι “το πρόβλημα του περιοδεύοντος πωλητή (traveling salesman problem)”. Με λίγα λόγια σας δίνουν μία λίστα με πόλεις και τις αποστάσεις μεταξύ τους και σας ζητάνε να επισκευθείτε όλες τις πόλεις κάνοντας όσο λιγότερα χιλιόμετρα γίνεται. Η αλήθεια είναι ότι δε φαίνεται τρομερά δύσκολο, αλλά αυτό είναι ένα ακόμα χαρακτηριστικό των προβλημάτων που ανήκουν στην κλάση NP. Συνήθως είναι αρκετά εύκολο να τα κατανοήσουμε, αλλά δεν μπορούμε να βρούμε τρόπο να τα λύσουμε γρήγορα.

Νταξ μωρέ. Και τι έγινε;

Κάτι που παρατηρούμε είναι το εξής: όλα τα προβλήματα που είναι στο P είναι και στο NP (αν θέλετε να το πούμε και με μαθηματική ορολογία το P είναι υποσύνολο του NP). Αν μπορούμε να λύσουμε ένα πρόβλημα σε πολυωνυμικό χρόνο, μπορούμε να ελέγξουμε και τη λύση του σε πολυωνυμικό χρόνο: Απλά την υπολογίζουμε και ξέρουμε ότι είναι σωστή! Άρα όταν μιλάμε για προβλήματα που είναι στο NP εννοούμε αυτά που δεν είναι στο P, σωστά;

Ε… εδώ είναι που ως Επιστήμονες Υπολογιστών και Μαθηματικοί αισθανόμαστε μία μικρή αμηχανία… Δεν ξέρουμε! Δεν είμαστε σίγουροι αν τα προβλήματα που είναι στο NP μπορούν να λυθούν σε πολυωνυμικό χρόνο. Απλά ξέρουμε ότι δεν έχουμε βρει τρόπο μέχρι τώρα να το κάνουμε.

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

Και αυτή είναι η ερώτηση του 1 εκατομυρίου δολαρίων (κυριολεκτικά): Είναι το P ίσο με το NP; Δηλαδή να δείξουμε ότι έστω και ένα πρόβλημα που είναι στο NP δεν είναι στο P (που θα έδειχνε ότι δεν είναι ίσα), ή ότι όλα τα προβλήματα του NP είναι και στο P (που θα έδειχνε ότι είναι ίσα). Μία πρόσφατη δημοσκόπηση μεταξύ διάσημων θεωρητικών της Επιστήμης των Υπολογιστών έδειξε ότι 61% πιστεύουν πως ΝΡ και Ρ δεν είναι ίσα, 9% θεωρούν πως είναι ίσα, 22% δεν έχουν γνώμη και 8% πιστεύουν κάτι πιο πολύπλοκο, αλλά ιδιαιτέρως ενδιαφέρον. Αν ξεβαρεθώ και δω ότι αυτό το post δημιούργησε ένα σχετικό ενδιαφέρον, ίσως και να γράψω κάτι για την τελευταία άποψη.

Να λοιπόν ένας καλός τρόπος να βγάλετε ένα γρήγορο μύριο 😉

Η έμπνευση, και αρκετό από το υλικό της παραπάνω παρουσίασης προήλθαν από ένα σχόλιο στο reddit.

Κοντός σύνδεσμος αλληλούια: http://wp.me/p1yMcy-65

Advertisements
This entry was posted in Διάφορα, Επιστήμη-Υπολογιστών, Μαθηματικά. Bookmark the permalink.

5 Responses to Είναι το P ίσο με το NP? Ιδού η απορία!

  1. Τι εννοείς ότι πιστεύουν ότι είναι κάτι πιο πολύπλοκο;;

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

    • Μια ιδέα πήρες όμως; Να σου θυμίσω ότι ο Goedel κατέληξε στο τρελάδικο και πέθανε από ασιτία γιατί φοβόταν ότι θα τον δηλητηριάσουν…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s