Πρόβλημα P=NP

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

Ουσιαστικά, αναφέρεται για πρώτη φορά σε μια επιστολή που γράφτηκε το 1956 από τον Κουρτ Γκέντελ στον Τζον φον Νόιμαν. Ο Γκέντελ ρώτησε αν ένα ορισμένο NP πλήρες πρόβλημα (το οποίο σημαίνει ότι μια οποιαδήποτε λύση μπορεί εύκολα να ελεγχθεί για το αν ικανοποιεί τις συνθήκες του προβλήματος) θα μπορούσε να λυθεί σε τετραγωνικό ή γραμμικό χρόνο.^[2] Η ακριβής δήλωση του προβλήματος P vs NP εισήχθη το 1971 από τον Στήβεν Κουκ στη δημοσίευσή του «Η πολυπλοκότητα θεωρημάτων αποδεικτικών διαδικασιών»^[3] και θεωρείται από πολλούς ως το πιο σημαντικό ανοικτό πρόβλημα στον τομέα αυτό.^[4] Πρόκειται για ένα από τα επτά προβλήματα του βραβείου Μιλλέννιουμ (Millennium Prize) από το Ινστιτούτο Μαθηματικών Κλέι (Clay Mathematics Institute) με αμοιβή 1 εκατομμύριο δολάρια για την πρώτη σωστή λύση.

Ο όρος γρήγορα, που χρησιμοποιήθηκε παραπάνω, δηλώνει την ύπαρξη ενός αλγορίθμου για μια διαδικασία ή οποία τρέχει σε πολυωνυμικό χρόνο. Η γενική κλάση ερωτημάτων για το οποίο κάποιος αλγόριθμος δίνει την απάντηση σε πολυωνυμικό χρόνο ονομάζεται "κλάση P" ή απλούστερα "P". Για κάποια ερωτήματα δεν υπάρχει γνωστός τρόπος για την γρήγορη εύρεση απάντησης, αλλά αν κάποιος διαθέτει πληροφορίες που να αποδεικνύουν ποια είναι η απάντηση, είναι δυνατό να επιβεβαιώσει την απάντηση γρήγορα. Η κλάση των προβλημάτων που μπορούν να "επιβεβαιωθούν" σε πολυωνυμικό χρόνο ονομάζεται κλάση NP.

Μια περίπτωση αποτελεί το πρόβλημα αθροίσματος υποσυνόλου, ένα παράδειγμα προβλήματος που είναι εύκολο να επιβεβαιωθεί,του οποίου,όμως, η λύση μπορεί να είναι δύσκολο να υπολογιστεί. Δοθέντος ενός συνόλου ακεραίων, υπάρχει κάποιο μη κενό υποσύνολο που να αθροίζει στο 0; Για παράδειγμα, υπάρχει υποσύνολο του συνόλου {−2, −3, 15, 14, 7, −10} που να αθροίζει στο 0; Η απάντηση "ναι, επειδή το υποσύνολο {−2, −3, −10, 15} αθροίζει στο 0" μπορεί γρήγορα να επιβεβαιωθεί με τρεις προσθέσεις. Ωστόσο,δεν υπάρχει γνωστός αλγόριθμος που να βρίσκει τέτοια υποσύνολα σε πολυωνυμικό χρόνο (υπάρχει ένας, παρόλα αυτά, σε εκθετικό χρόνο, που αποτελείται απο 2ⁿ-n-1 προσπάθειες), αλλά τέτοιος αλγόριθμος υπάρχει αν P = NP. Συνεπώς το πρόβλημα είναι NP (γρήγορα ελέγξιμο) αλλά όχι απαραίτητα P (γρήγορα επιλύσιμο).

Μια απάντηση στο ερώτημα P = NP θα καθόριζε αν προβλήματα που μπορούν να επιβεβαιωθούν σε πολυωνυμικό χρόνο, όπως το πρόβλημα αθροίσματος υποσυνόλου, μπορούν και να λυθούν σε πολυωνυμικό χρόνο. Αν αποδειχθεί ότι P ≠ NP, θα σημαίνει ότι υπάρχει προβλήματα στην NP (όπως τα NP-πλήρη προβλήματα) τα οποία είναι δυσκολότερο να υπολογιστούν από το να επιβεβαιωθούν. Δεν θα μπορούν να υπολογιστούν σε πολυωνυμικό χρόνο αλλά η απάντηση μπορεί να επιβεβαιωθεί σε πολυωνυμικό χρόνο.

Εκτός από το να είναι ένα σημαντικό πρόβλημα στην Θεωρία Υπολογισμού, μια απόδειξη του θα εχει σημαντικές επιρροές στα Μαθηματικά, την Κρυπτογραφία, την μελέτη Αλγορίθμων, την Τεχνητή Νοημοσύνη, την Θεωρία Παιγνίων, την Φιλοσοφία, τα Οικονομικά και πολλά άλλα πεδία.

Περιεχόμενο

Η σχέση μεταξύ των κλάσεων πολυπλοκότητας P και NP αποτελεί αντικείμενο μελέτης της Θεωρίας Πολυπλοκότητας, το κομμάτι της Θεωρίας Υπολογισμού που αντιμετωπίζει υπολογιστικούς τρόπους για την επίλυση ενός προβλήματος. Συνήθεις αναφορές της πολυπλοκότητας είναι ο χρόνος (πόσα βήματα χρειάζονται για την επίλυση του προβλήματος) και ο χώρος (πόση μνήμη χρειάζεται για την επίλυση του προβλήματος).

Για μια τέτοια μελέτη, απαιτείται το μοντέλο ενός υπολογιστή για τον οποίο πρέπει να αναλυθεί ο χρόνος εκτέλεσης. Τυπικά, τέτοια μοντέλα υποθέτουν ότι ο υπολογιστής είναι προσδιοριστός (δοθείσας της παρούσας κατάστασης ενός υπολογιστικού μοντέλου και οποιασδήποτε εισόδου, υπάρχει μοναδική δράση την οποία μπορεί να εκτελέσει το μοντέλο) και είναι ακολουθιακή (εκτελεί δράσεις την μία μετά την άλλη).

Σε αυτήν την θεωρία, η κλάση P αποτελείται από όλα τα προβλήματα απόφασης τα οποία μπορούν να επιλυθούν από μια προσδιοριστική ακολουθιακή μηχανή σε χρόνο ο οποίος είναι πολυωνυμικός στο μέγεθος της εισόδου. Η κλάση NP αποτελείται από όλα τα προβλήματα απόφασης των οποίων οι λύσεις μπορούν να επιβεβαιωθούν σε πολυωνυμικό χρόνο με δεδομένο τις σωστές πληροφορίες, ή ισοδύναμα, των οποίων οι λύσεις μπορούν να βρεθούν σε πολυωνυμικό χρόνο σε μια μη-προσδιοριστή μηχανή.^[5] Είναι σαφές ότι, P ⊆ NP. Το μεγαλύτερο ανοικτό ερώτημα στην Θεωρητική Πληροφορική είναι η σχέση μεταξύ των δύο κλάσεων:

Ισχύει P = NP;

Σε μια δημοσκόπηση το 2002, όπου έλαβαν μέρος 100 ερευνητές, 61 πιστεύουν ότι η απάντηση είναι όχι, 9 πίστευαν ότι η απάντηση είναι ναι, και 22 δεν ήταν σίγουροι. 8 πίστευαν ότι η ερώτηση μπορεί να είναι ανεξάρτητη από τα ως τώρα αποδεκτά αξιώματα και άρα αδύνατη να αποδειχθεί ή να αμφισβητηθεί.^[6]

Το 2012, 10 χρόνια μετά, η ίδια δημοσκόπηση επαναλήφθηκε. Ο αριθμός των ερευνητών που απάντησαν ήταν 151: 126 (83%) πίστευαν ότι η απάντηση είναι οχι, 12 (9%) πίστευαν ότι η απάντηση είναι ναι, 5 (3%) πίστευαν ότι η ερώτηση μπορεί να είναι ανεξάρτητη από τα ως τώρα αποδεκτά αξιώματα και άρα αδύνατη να αποδειχθεί ή να αμφισβητηθεί, 8 (5%) απάντησαν είτε ότι δεν γνωρίζουν είτε ότι δεν τους ενδιαφέρει είτε ότι δεν θέλουν ούτε η απάντηση να είναι ναι ούτε το πρόβλημα να επιλυθεί.^[7]

NP πληρότητα

Διάγραμμα Euler για P, NP, NP-πλήρη και NP-δύσκολα σύνολα προβλημάτων.

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

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

Για παράδειγμα, το πρόβλημα ελέγχου της ικανοποιησιμότητας λογικών εκφράσεων είναι ένα NP-πλήρες πρόβλημα από το θεώρημα Cook–Levin, έτσι ώστε κάθε περίπτωση κάποιου προβλήματος στην NP μπορεί να μετατραπεί μηχανικά σε περίπτωση προβλήματος ελέγχου ικανοποιησιμότητας λογικών εκφράσεων σε πολυωνυμικο χρόνο. Το πρόβλημα ελέγχου ικανοποιησιμότητας λογικών εκφράσεων είναι ένα από τα πολλά NP-πλήρη προβλήματα. Αν κάποιο NP-πλήρες πρόβλημα είναι στην P, τότε είναι επακόλουθο ότι P = NP. Δυστυχώς, πολλά σημαντικά προβλήματα έχουν αποδειχθεί να είναι NP-πλήρη, και δεν υπάρχει γνωστός γρήγορος αλγόριθμος για κανένα από αυτά.

Με βάση μόνο τον ορισμό δεν είναι προφανές ότι NP-πλήρη προβλήματα υπάρχουν. Ένα ασήμαντο NP-πλήρες πρόβλημα που επινοούμε δημιουργείται ως εξής: δεδομένης περιγραφής μιας μηχανής Turing M με εγγύηση ότι θα σταματήσει σε πολυωνυμικό χρόνο, υπάρχει ένα πολυωνυμικού μεγέθους δεδομένο εισόδου που θα αποδεχτεί η Μ;^[8] Είναι στην NP επειδή (αν δοθεί δεδομένο εισόδου) είναι απλό να ελεγχθεί αν η Μ δέχεται το δεδομένο εισόδου, προσομοιώνοντας την M. Είναι NP-πλήρες επειδή το μέσο επιβεβαίωσης για μια συγκεκριμένη περίπτωση ενός προβλήματος στην NP μπορεί να θεωρηθεί σαν μια πολυωνυμικού χρόνου μηχανή Μ, η οποία δέχεται την λύση σαν δεδομένο για να την επιβεβαιώσει. Τότε η ερώτηση αν η περίπτωση είναι "ναι ή όχι" περίπτωση, προσδιορίζεται από το αν υπάρχει έγκυρο δεδομένο εισόδου.

Το πρώτο φυσικό πρόβλημα που αποδείχθηκε ότι είναι NP-πλήρες ήταν το πρόβλημα ελέγχου ικανοποιησιμότητας λογικών εκφράσεων. Όπως ειπώθηκε παραπάνω, αυτό είναι το θεώρημα Cook–Levin. Η απόδειξη ότι η ικανοποιησιμότητα είναι NP-πλήρες περιέχει τεχνικές λεπτομέρειες σχετικά με μηχανές Turing,αφού αυτές σχετίζονται με τον ορισμό της NP. Ωστόσο, αφού αποδείχθηκε πως αυτό το πρόβλημα είναι NP-πλήρες, απόδειξη με αναγωγή έδωσε έναν πιο απλό τρόπο να αποδειχθεί ότι πολλά άλλα προβλήματα είναι επίσης NP-πλήρη, συμπεριλαμβανομένου του προβλήματος αθροίσματος υποσυνόλου που αναφέρθηκε πριν. Έτσι, ένα μεγάλο πλήθος φαινομενικά ανόμοιων προβλημάτων είναι όλα αναγώγιμα αναμεταξύ τους, και είναι κατά μία έννοια "το ίδιο πρόβλημα".

Δυσκολότερα προβλήματα

Παρόλο που είναι άγνωστο αν P = NP, προβλήματα εκτός της P γνωστά. Ένας αριθμός σύντομων και σαφών προβλημάτων (προβλήματα που δεν λειτουργούν με κανονικές εισόδους, αλλά με μια υπολογιστική περιγραφή των εισόδων) είναι γνωστά ως EXPTIME -πλήρη. Επειδή μπορεί να αποδειχθεί ότι P ⊊ EXPTIME,αυτά τα προβλήματα είναι έξω από την P, και έτσι απαιτούν παραπάνω από πολυωνυμικό χρόνο. Στην πραγματικότητα, από το θεώρημα ιεράρχησης χρόνου, δεν μπορούν να επιλυθούν σε σημαντικά λιγότερο χρόνο από τον εκθετικό. Τέτοια παραδείγματα περιλαμβάνουν μια τέλεια στρατηγική για το σκάκι (σε N × N ταμπλό)^[9] και σε άλλα επιτραπέζια.^[10]

Το πρόβλημα απόφασης της εγκυρότητας μια δήλωσης στην αριθμητική Presburger απαιτεί ακόμα περισσότερο χρόνο. Οι Fischer και Rabin απέδειξαν το 1974 ότι κάθε αλγόριθμος που αποφασίζει την εγκυρότητα μιας δήλωσης Presburger "τρέχει" για χρόνο τουλάχιστον $2^{2^{cn}}$ για κάποια σταθερά c. Εδώ, n είναι το μήκος της δήλωσης Presburger. Έτσι, είναι γνωστό ότι το πρόβλημα χρειάζεται παραπάνω από εκθετικό χρόνο εκτέλεσης. Ακόμα πιο δύσκολα είναι τα μη αποφασίσιμα προβλήματα, όπως το πρόβλημα τερματισμού. Δεν μπορούν να επιλυθούν πλήρως από έναν αλγόριθμο, με την έννοια ότι για οποιονδήποτε συγκεκριμένο αλγόριθμο υπάρχει τουλάχιστον μία είσοδος για την οποία ο αλγόριθμος δεν θα παράγει το σωστό αποτέλεσμα. Είτε θα δώσει λάθος αποτέλεσμα , τελειώνοντας χωρίς να δώσει τελική απάντηση, είτε θα εκτελείται επ' άπειρον χωρίς να παράγει αποτέλεσμα.

NP Προβλήματα τα οποία δεν είναι γνωστό αν είναι P ή NP-πλήρη

Απεδείχθη από τον Ladner ότι αν P ≠ NP τότε υπάρχουν προβλήματα στην NP τα οποία δεν ανήκουν στην P ούτε είναι NP-πλήρη.^[1] Τέτοια προβλήματα λέγονται NP-ενδιάμεσα. Το πρόβλημα γραφήματος ισομορφισμού, το πρόβλημα διακριτού λογαρίθμου και το πρόβλημα παραγοντοποίησης ακεραίου είναι προβλήματα τα οποία πιστεύεται ότι είναι NP-ενδιάμεσα. Είναι κάποια από τα πολύ λίγα NP προβλήματα για τα οποία δεν είναι γνωστό αν είναι P ή NP-πλήρη.

The πρόβλημα γραφήματος ισομορφισμού είναι ένα υπολογιστικό πρόβλημα για τον προσδιορισμό εάν δύο πεπερασμένα γραφήματα είναι ισόμορφα. Ένα σημαντικό άλυτο πρόβλημα στην Θεωρία Πολυπλοκότητας είανι εάν το πρόβλημα ισομορφισμού γραφημάτων είναι P, NP-πλήρες ή NP-ενδιάμεσο. Η απάντηση δεν είναι γνωστή και πιστεύεται ότι το πρόβλημα τουλάχιστον δεν είναι NP-πλήρες.^[11] Αν ο ισομορφισμός γραφήματος είναι NP-πλήρης, τότε η πολυωνυμική ιεραρχία του χρόνου καταρρέει στο δεύτερο επίπεδο.^[12]^[13] Επειδή είναι ευρέως αποδεκτό ότι η πολυωνυμική ιεραρχία του χρόνου δεν καταρρέει σε πεπερασμένο επίπεδο το πρόβλημα ισομορφισμού γραφημάτων δεν είναι NP-πλήρες. Ο βέλτιστος αλγόριθμος για αυτό το πρόβλημα , των Laszlo Babai και Eugene Luks έχει χρόνο εκτέλεσης 2^{O(√nlog(n))} για γραφήματα με n κορυφές.

Το πρόβλημα παραγοντοποίησης ακεραίου είναι ένα υπολογιστικό πρόβλημα για τον προσδιορισμό των πρώτων παραγόντων ενός γνωστού ακεραίου. Εκφρασμένο ως ένα πρόβλημα απόφασης, είναι ένα πρόβλημα για την απόφαση εάν η είσοδος έχει παράγοντα μικρότερο από k. Δεν είναι γνωστός κάποιος αποδοτικός αλγόριθμος παραγοντοποίησης ακεραίου και αυτή η βάση προκύπτει από πολλά μοντέρνα συστήματα κρυπτογράφησης, όπως το RSA. Το πρόβλημα είναι της κλάσης NP και της co-NP^[14]). Άν το πρόβλημα είναι NP-πλήρες, τότε η ιεραρχία πολυωνυμικού χρόνου καταρρέει στο αρχικό επίπεδο.Ο βέλτιστος γνωστός αλγόριθμος για παραγοντοποίηση ακεραίου είναι tο γενικό κόσκινο σώματος αριθμών, με αναμενόμενο χρόνο εκτέλεσης

O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)

για την παραγοντοποίηση ενός ακεραίου n' ψηφίων.

P σημαίνει "εύκολο";

Το γράφημα δείχνει τον χρόνο(μέσος χρόνος από 100 δείγματα σε ms χρησιμοποιόντας έναν επεξεργαστή 933 MHz Pentium III) ενάντια προβλήματος μεγέθους για τα προβλήματα σακίδιου για ένα εξειδικευμένο αλγόριθμο state-of-the-art. Δευτεροβάθμια εφαρμογή υποδηλώνει ότι η εμπειρική αλγοριθμική πολυπλοκότητα για τις περιπτώσεις με 50-10.000 μεταβλητές είναι O((log(n))²).^[15]

Όλη η προηγούμενη συζήτηση έχει οδηγήσει στην υπόθεση πως P σημαίνει "εύκολο" και "όχι P" σημαίνει "δύσκολο",μία υπόθεση γνωστή ως θέση του Cobham. Είναι συνηθισμένη και λογικά ακριβής υπόθεση στην θεωρία πολυπλοκότητας. Ωστόσο, έχει κάποιους περιορισμούς.

Αρχικά, δεν είναι πάντα αληθής στην πράξη. Ένας θεωρητικός πολυωνυμικός αλγόριθμος μπορεί να έχει πολύ μεγάλους σταθερούς παράγοντες ή εκθετικούς καθιστώντας την ανέφικτη. Από την άλλη πλευρά, ακόμα κι αν ένα πρόβλημα αποδειχθεί να είναι NP-πλήρες, ακόμα κι αν P ≠NP, μπορεί να υπάρχουν αποδοτικές προσεγγίσεις για να αντιμετωπίσουμε το πρόβλημα στην πράξη. Υπάρχουν αλγόριθμοι για πολλά NP-πλήρη προβλήματα, όπως το πρόβλημα του σακιδίου, το πρόβλημα του περιπλανώμενου πωλητή και το πρόβλημα ελέγχου ικανοποιησιμότητας λογικών εκφράσεων, που μπορούν να λύσουν στο βέλτιστο κάποια προβλήματα τη πραγματικότητας σε λογικό χρονικό διάστημα. Η εμπειρική πολυπλοκότητα μέσου προβλήματος (χρόνος εναντίον μεγέθους προβλήματος) τέτοιων αλγορίθμων μπορεί να είναι εκπληκτικά μικρή. Ένα παράδειγμα είναι ο αλγόριθμος simplex στον γραμμικό προγραμματισμό, ο οποίος δουλεύει εκπληκτικά καλά στην πράξη. Παρόλο που έχει την χειρότερη περίπτωση πολυπλοκότητας χρόνου εκθετικά, εκτελείται το ίδιο γρήγορα με τους καλύτερους αλγορίθμους πολυωνυμικού χρόνου.^[16]

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

Λόγοι για να πιστεύουμε ότι P ≠ NP

Σύμφωνα με γκάλοπ,^[6][17] πολλοί επιστήμονες της πληροφορικής πιστεύουν ότι P ≠ NP. Ένας λόγος-"κλειδί" για την πεποίθηση αυτή είναι ότι μετά από δεκαετίες μελέτης αυτών των προβλημάτων, κανείς δεν μπόρεσε να βρει αλγόριθμο πολυωνυμικού χρόνου για περισσότερα από 3000 σημαντικά γνωστά NP-πλήρη προβλήματα (δείτε τη λίστα NP-πλήρεις προβλημάτων). Αυτοί οι αλγόριθμοι αναζητήθηκαν πολύ πριν οριστεί η ιδέα της NP-πληρότητας (τα 21 NP-πλήρη προβλήματα του Karp, από τα πρώτα που βρέθηκαν, ήταν όλα γνωστά υπάρχοντα προβλήματα τον καιρό που αποδείχτηκε πως είναι NP-πλήρη). Επιπλέον, το αποτέλεσμα P = NP θα υπονοούσε πολλά άλλα καταπληκτικά αποτελέσματα τα οποία τώρα θεωρούνται ψευδή,όπως NP = co-NP και P = PH.

Είναι επίσης διαισθητικά ισχυριζόμενο, ότι η ύπαρξη προβλημάτων τα οποία είναι δύσκολο να λυθούν, αλλά για τα οποία οι λύσεις είναι εύκολο να επιβεβαιωθούν, ταιριάζει με την εμπειρία της καθημερινότητας.^[18]

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

— Scott Aaronson, MIT

Από την άλλη μεριά, κάποιοι μελετητές πιστεύουν πως υπάρχει υπεραισιοδοξία στην πίστη πως P ≠ NP και ότι οι μελετητές θα πρέπει να αναζητήσουν αποδείξεις ότι P = NP. Για παράδειγμα, το 2002 παρουσιάστηκαν αυτές οι δηλώσεις:^[6]

Το κύριο επιχείρημα υπέρ του P ≠ NP είναι η έλλειψη θεμελιώδους εξέλιξης στην περιοχή των εξαντλητικών ερευνών. Αυτό είναι, κατά τη γνώμη μου, ένα πολύ αδύναμο επιχείρημα. Ο χώρος των αλγορίθμων είναι πολύ μεγάλος και είμαστε μόνο στην αρχή της εξερεύνησης του. [...] Η ανάλυση του τελευταίου θεωρήματος του Fermat δείχνει επίσης ότι πολύ απλές ερωτήσεις μπορούν να απαντηθούν μόνο από βαθιές θεωρίες.

—Moshe Y. Vardi, Rice University

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

—Anil Nerode, Cornell University

Συνέπειες της λύσης

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

P = NP

Μια απόδειξη ότι P = NP θα μπορούσε να έχει εκπληκτικά πρακτικές συνέπειες, εάν οι αποδείξεις οδηγήσουν σε αποτελεσματικές μεθόδους για την επίλυση ορισμένων από τα σημαντικότερα προβλήματα της κλάσης 'NP' . Είναι επίσης πιθανό ότι η απόδειξη αυτή δεν θα οδηγήσει άμεσα σε αποτελεσματικές μεθόδους, ίσως, αν η απόδειξη είναι μη εποικοδομητική ή το μέγεθος του πολυωνύμου οριοθέτησης είναι πολύ μεγάλο για να είναι αποτελεσματική στην πράξη. Οι συνέπειες, τόσο θετικές όσο και αρνητικές, προκύπτουν αφού διάφορα 'NP' -πλήρη προβλήματα είναι θεμελιώδους σημασίας σε πολλούς τομείς.

Η Κρυπτογραφία, για παράδειγμα, βασίζεται σε ορισμένα προβλήματα που είναι δύσκολα. Το πόσο μια εποικοδομητική και αποτελεσματική λύση θα πρέπει να αποτελέσει απειλή για την κρυπτογραφία εξαρτάται από τις λεπτομέρειες. Μια λύση τάξης $O(N^{2})$ ή καλύτερη και ένας εύλογος σταθερός όρος θα ήταν καταστροφική.

Αποτελέσματα πάνω στη δυσκολία της απόδειξης

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

Ένα επιπλέον στοιχείο για τη δυσκολία του προβλήματος αποτελεί το γεγονός πως όλες οι γνωστές τεχνικές απόδειξης στη Υπολογιστική Πολυπλοκότητα ανήκουν σε μια από τις παρακάτω κατηγορίες, καμιά από τις οποίες δεν είναι ικανή να αποδείξει πως P ≠ NP:

Κατηγοριοποίηση	Ορισμός
Σχετικοκοποιητική απόδειξη	Φανταστείτε έναν κόσμο όπου κάθε αλγόριθμος επιτρέπεται να κάνει ερωτήματα σε μια συγκεκριμένη υπορουτίνα που καλείται χρησμοδοτική μηχανή Turing, και ο χρόνος εκτέλεσης της μηχανής δεν συνυπολογίζεται στο χρόνο εκτέλεσης του αλγορίθμου. Οι περισσότερες αποδείξεις (κυρίως οι κλασικές) εφαρμόζονται ομοιόμορφα σε έναν κόσμο με τέτοιες μηχανές ανεξαρτήτως με το τι κάνει η μηχανή. Αυτές οι αποδείξεις καλούνται σχετικοποιητικές. Το 1975 οι Baker, Gill και Solovay έδειξαν πως P = NP ως προς συγκεκριμένες μηχανές, ενώ P ≠ NP ως προς κάποιες άλλες.^[17] Από τη στιγμή που οι σχετικοποιητικές αποδείξεις μπορούν να αποδείξουν μόνο προτάσεις που είναι ομοιόμορφα αληθείς για κάθε πιθανή μηχανή, αυτό μας αποδεικνύει πως οι σχετικοποιητικές τεχνικές δε μπορούν να επιλύσουν το P = NP.
Φυσικές αποδείξεις	Το 1993, οι Alexander Razborov και Steven Rudich όρισαν μια γενική κλαση τεχνικών αποδείξεων για τον υπολογισμό κατώτατων ορίων στην πολυπλοκότητα κυκλωμάτων την οποία ονόμασαν φυσικές αποδείξεις. Πήραν αυτήν την ονομασία επειδή βασίζονται στις φυσικές ιδιότητες των κυκλωμάτων. Εκείνη τη στιγμή όλα τα προηγούμενα γνωστά κατώτερα όρια των κυκλωμάτων ήταν φυσικά και η πολυπλοκότητα κυκλωμάτων θεωρούνταν μια αρκετά υποσχόμενη προσέγγιση για την επίλυση του P = NP. Παρ' όλα αυτά οι Razborov και Rudich έδειξαν πως αν υπάρχουν μονόδρομες συναρτήσεις, τότε καμιά φυσική μέθοδος απόδειξης δε μπορεί να διακρίνει το P από το NP. Ανη ύπαρξη μονόδρομων συναρτήσεων δεν έχει επισήμως αποδειχθεί, οι περισσότεροι μαθηματικοί πιστεύουν πως υπάρχουν, και μια απόδειξης της ύπαρξης ή μη αυτών των συναρτήσεων αποτελεί μια πιο ισχυρή πρόταση από τη συσχέτιση του P με το NP. Συνεπώς είναι μάλλον απίθανο οι φυσικές αποδείξεις από μόνες τους να επιλύσουν το P = NP.
Αλγεβρικές Αποδείξεις	Μετά τα αποτελέσματα των Baker-Gill-Solovay, νέες μη-σχετικοποιητικές τεχνικές απόδειξης χρησιμοποιήθηκαν επιτυχημένα για να αποδείξουν πως IP = PSPACE. Παρ' όλα αυτά, το 2008, οι Scott Aaronson και Avi Wigderson έδειξαν πως η βασική τεχνική που χρησιμοποιείται στην απόδειξη IP = PSPACE, γνωστή ως αριθμητικοποίηση, ήταν επίσης ανίκανη να αποδείξει πως P = NP.^[18]

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

Αυτά τα εμπόδια έχουν επίσης οδηγήσει τους τους επιστήμονες πληροφορικής στο συμπέρασμα πως το πρόβλημα P εναντίον NP μπορεί να είναι ανεξάρτητο των τυπικών αξιωματικών συστημάτων όπως το ZFC (δε μπορεί να αποδειχθεί ή να απορριφθεί μέσα τους). Η ερμηνεία ενός ανεξάρτητου αποτελέσματος θα μπορούσε να είναι πως είτε δεν υπάρχει αλγόριθμος πολυωνυμικού χρόνου για κάθε NP-πλήρες πρόβλημα, και συνεπώς μια τέτοια απόδειξη δε μπορεί να κατασκευασθεί στο (π.χ.) ZFC, ή πως οι αλγόριθμοι πολυωνυμικού χρόνου για τα NP-πλήρη προβλήματα μπορεί να υπάρχουν, αλλά είναι αδύνατο να αποδείξουμε στο ZFC ότι αυτοί οι αλγόριθμοι είναι σωστοί.^[19] Παρ' όλα αυτά, αν μπορεί να αποδειχθεί, χρησιμοποιώντας τις υπάρχουσες τεχνικές, πως το πρόβλημα δε μπορεί να επιλυθεί ακόμη και με πιο αδύναμες παραδοχές επεκτείνοντας τα Αξιώματα Πεάνο (ΑΠ) για αριθμητική ακεραίων, τότε θα ήταν απαραίτητο να υπάρχουν αλγόριθμοι σχεδόν-πολυωνυμικού χρόνου για κάθε πρόβλημα στο NP.^[20] Συνεπώς , αν κάποιος πιστεύει (όπως κάνουν οι περισσότεροι θεωρητικοί πολυπλοκότητας) πως δεν έχουν όλα τα προβλήματα στο NP αποδοτικούς αλγορίθμους, αυτό θα σήμαινε πως οι αποδείξεις ανεραρτησίας χρησιμοποιώντας αυτές τις τεχνικές δεν είναι δυνατές. Επιπλέον, αυτό το αποτέλεσμα υποδεικνύει πως το να αποδείξει κανείς την ανεξαρτησία από τα ΑΠ ή το ZFC χρησιμοποιώντας τις ήδη γνωστές τεχνικές δεν είναι ευκολότερο από το να αποδείξεις την ύπαρξη αποδοτικών αλγορίθμων για όλα τα προβλήματα στο NP.

Θα έπρεπε επίσης να σημειωθεί πως υπάρχουν προτάσεις που είναι ανεξάρτητες στο ZFC και δεν είναι δυνατόν να επαληθευθούν ως τέτοιες από οποιαδήποτε μηχανή Τούρινγκ και υπό αυτή την έννοια είναι πιθανό για ένα πρόβλημα να μην είναι ποτέ δυνατό να επαληθευθεί ως αληθές, ψευδές, ή ακόμη και ανεξάρτητο του ZFC. Δεν είναι ακόμη γνωστό αν το P = NP είναι ή όχι ένα τέτοιο πρόβλημα.^[21]

Ισχυριζόμενες Λύσεις

Ενώ το πρόβλημα P εναντίον NP θεωρείται γενικά άλυτο,^[22] πολλοί ερασιτέχνες και μερικοί επαγγελματίες ερευνητές έχουν ισχυριστεί κατά καιρούς πως το έχουν επιλύσει. Ο Woeginger έχει δημοσιεύσει μια ολοκληρωμένη λίστα.^[23] Τον Αύγουστο του 2010 ένας ισχυρισμός πως απεδείχθη ότι P ≠ NP, από τον Vinay Deolalikar, ερευνητή στα HP Labs, Palo Alto, απέκτησε μεγάλη δημοσιότητα στο διαδίκτυο και στον τύπο αφού είχε αρχικά χαρακτηρισθεί πως "φαίνεται να είναι μια σχετικά σοβαρή προσπάθεια" από δυο ειδικούς του χώρου.^[24] Η απόδειξη αναλύθηκε δημόσια από ακαδημαϊκούς,^[25]^[26] και ο Neil Immerman, ένας ειδικός στο πεδίο, υπέδειξε δυο πιθανά μοιραία σφάλματα στην απόδειξη.^[27] Το Σεπτέμβριο του 2010, ο Deolalikar ισχυρίστηκε πως δούλευε σε μια αναλυτική επέκταση της απόδειξής του.^[28] Παρ' όλα αυτα οι γνώμες που εκφράστηκαν από πολλούς επιφανείς επιστήμονες θεωρητικής πληροφορικής συγκλίνουν στο ότι η συγκεκριμένη απόδειξη δεν είναι σωστή αλλά ούτε και προσφέρει κάποια πρόοδο στην κατανόηση του προβλήματος.^[29] Αυτό το συμπέρασμα οδήγησε το Μάιο του 2013 ένα άρθρο του The New Yorker να χαρακτηρίσει την απόπειρα απόδειξης ως "πλήρως ανυπόληπτη."^[30]

Λογικοί Χαρακτηρισμοί

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

Θεωρείστε όλες τις γλώσσες πεπερασμένων δομών με σταθερή υπογραφή, συμπεραλβανόμενης μιας σχέσης γραμμικής τάξης. Τότε, όλες οι γλώσσες που ανήκουν στην κλάση P μπορούν να εκφραστούν στην λογική πρώτης τάξης με την πρόσθεση ενός κατάλληλου σημείου συνδυασμών(fixed-point combinator).

Με τον ίδιο τρόπο, η κλάση NP είναι το σύνολο όλων των γλωσσών που μπορεί να εκφραστεί σε υπαρξιακή λογική δεύτερης τάξης, Δηλαδή, η λογική δεύτερης τάξης περιορίζεται να αποκλείσει την καθολική ποσοτικοποίηση πάνω στις σχέσεις, τις λειτουργίες και τα υποσύνολα. Οι γλώσσες στην πολυώνυμο ιεραρχία 'PH' , αντιστοιχούν σε όλες τις λογικές δεύτερης τάξης. Έτσι, το ερώτημα "είναι 'P' ένα κατάλληλο υποσύνολο του 'NP' » μπορεί να επαναδιατυπωθεί ως «είναι η υπαρξιακή λογική δεύτερης τάξης σε θέση να περιγράψει τις γλώσσες (πεπερασμένων γραμμικά διατεταγμένων δομών με μη τετριμμένη υπογραφή) ότι η λογική πρώτης τάξης με τουλάχιστον σταθερό σημείο δεν μπορούν; ».,^[31] .

Αλγόριθμοι Πολυωνυμικού Χρόνου

Για κάθε NP-πλήρες πρόβλημα δεν υπάρχει γνωστός αλγόριθμος που να τρέχει σε πολυωνυμικό χρόνο. Ωστόσο, υπάρχουν αλγόριθμοι για NP-πλήρη προβλήματα με την ιδιότητα ότι αν P = NP, τότε ο αλγόριθμος τρέχει σε πολυωνυμικό χρόνο(αν και με τεράστιες σταθερές, κάνοντας τον αλγόριθμο άσκοπο). Ο παρακάτω αλγόριθμος, που οφείλεται στον Leonid Levin, αποτελεί ένα τέτοιο παράδειγμα. Δέχεται μια NP-πλήρη γλώσσα SUBSET-SUM. Τρέχει σε πολυωνυμικό χρόνο αν και μόνο εάν P = NP:

// Αλγόριθμος που δέχεται μια 'NP-πλήρη γλώσσα SUBSET-SUM.
//
// αυτός είναι ένας πολυωνυμικός αλγόριθμος αν και μόνο εάν P = NP.
//
// "Πολυωνυμικός Χρόνος" σημαίνει ότι επιστρέφει "ναι" σε πολυωνυμικό χρόνο όταν
// η απάντηση είναι "ναι", τρέχει για πάντα όταν είναι "όχι".
//
// Είσοδος: S = πεπερασμένο σύνολο ακεραίων
// Έξοδος: "ναι" αν κάθε υποσύνολο του S αθροίζει στο 0.
// Διαφορετικά τρέχει για πάντα χωρίς έξοδο.
// Σημείωση: Το "Πρόγραμμα αριθμού P" είναι το πρόγραμμα που λαμβάνεται
// γράφοντας τον ακέραιο P στο δυαδικό, στη συνέχεια
// θεωρώντας την συμβολοσειρά των bits ως πρόγραμμα. 
// Κάθε πιθανό πρόγραμμα μπορεί να 
// δημιουργηθεί έτσι, αν και τα περισσότερα δεν κάνουν
// τίποτα λόγω συντακτικών λαθών. 

ΓΙΑ N = 1...∞
  ΓΙΑ P = 1...N
    Εκτέλεσε το πρόγραμμα αριθμού P για N βήματα με είσοδο S
    ΑΝ το πρόγραμμα δίνει ως έξοδο μια λίστα διακριτών ακαιρέων
      ΚΑΙ οι ακέραιοι ανήκουν στο S
      ΚΑΙ οι ακέραιοι αθροίζουν στο 0

    ΤΟΤΕ
      ΕΞΟΔΟΣ "ναι" και ΛΗΞΗ

Αν, και μόνο εάν, P = NP, τότε ο παραπάνω αλγόριθμος είναι αλγόριθμος πολυωνυμικού χρόνου που δέχεται μια NP-πλήρη γλώσσα. "Δέχεται" σημαίνει ότι δίνει απάντηση "ναι" σε πολυωνυμικό χρόνο, αλλά επιτρέπεται να εκτελείται διαρκώς όταν η απάντηση είναι "όχι"(επίσης γνωστό ως ημι-αλγόριθμος).

Αυτός ο αλγόριθμος είναι απίστευτα άσκοπος, ακόμα και αν P = NP. Είναι το συντομότερο πρόγραμμα που μπορεί να λύσει το SUBSET-SUM σε πολυωνυμικό χρόνο.

Επίσημοι ορισμοί

P και NP

Ένα πρόβλημα απόφασης είναι ένα πρόβλημα το οποία λαμβάνει ως είσοδο μια λέξη w επί ενός αλφαβήτου Σ, και δίνει ως έξοδο "ναι" ή "οχι". Αν υπάρχει ένας Αλγόριθμος (για παράδειγμα μια Μηχανή Τουρινγκ, ή ένα πρόγραμμα υπολογιστή με άπειρη μνήμη το οποία μπορεί να παράγει την σωστή απάντηση για κάθε λέξη εισόδου μήκους n ή στην χειρότερη cn^k βήματα, όπου k και c είναι σταθερές ανεξάρτητες από την λέξη εισόδου, τότε λέμε ότι το πρόβλημα απόφασης μπορεί να λυθεί σε πολυωνυμικό χρόνο και το εντάσουμε στην κλάση P. Αυστηρά, η κλάση P ορίζεται ως το σύνολο όλων των λέξεων οι οποίες μπορούν να αποφασιστούν από μια προσδιοριστική Μηχανή Τούρινγκ πολυωνυμικού χρόνου. Δηλαδή,

\mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}

όπου

L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}

Μια προσδιοριστή μηχανή Τούρινγκ πολυωνυμικού χρόνου είναι μια προσδιοριστή Μηχανή Τούρινγκ η οποία πληροί τα εξής κριτήρια:

M τερματίζει για κάθε w και
υπάρχει $k\in N$ τέτοιο ώστε $T_{M}(n)\in O(n^{k})$ , όπου Ο αναφέρεται στον ασυμπτωτικό συμβολισμό Big O και : $T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},\left|w\right|=n\}$

t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.

Η κλάση NP μπορεί να οριστεί με παρόμοι τρόπο μέσω μαις μη προσδιοριστής μηχανής Τούρινγκ(με τον παραδοσιακό τρόπο). Παρόλα αυτά, μια σύγχρονη προσέγγιση ορισμού της NP είναι η χρήση της ιδέας της πιστοποίησης και του ελέγχου. Επίσημα, η NP ορίζεται ως το σύνολο των λέξεων επί ενός πεπερασμένου αλφάβητου που έχει έναν επιβεβαιωτή ο οποίος τρέχει σε πολυωνυμικό χρόνο, όπου ο όρος επιβεβαιωτής ορίζεται ως εξής.

Έστω L μια γλώσσα επί αλφάβητου, Σ.

L ∈ NP αν, και μόνο αν, υπάρχει δυαδική σχέση και ένας θετικός ακέραιος k έτσι ώστε οι δύο παρακάτω συνθήκες ικανοποιούνται:

Για όλα τα $x\in \Sigma ^{*},x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ έτσι ώστε (x, y) ∈ R και $|y|\in O(|x|^{k})$ και
η γλώσσα $L_{R}=\{x\#y:(x,y)\in R\}$ επί του $\Sigma \cup \{\#\}$ αποφασίζεται από μηχανή Turing σε πολυωνυμικό χρόνο.

Μια μηχανή Turing που αποφασίζει L_R αποκαλείται επιβεβαιωτής της L και ένα y τέτοιο ώστε t (x, y) ∈ R καλείται πιστοποιητής μέλους του x στο L.

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

Παράδειγμα

Έστω $\mathrm {COMPOSITE} =\left\{x\in \mathbb {N} |x=pq\;{\text{for integers}}\;p,q>1\right\},R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} |1<y\leq {\sqrt {x}}\;{\text{and}}\;y\;{\text{divides}}\;x\right\}.$

Προφανώς, η ερώτηση αν ένα δεδομένο x είναι σύνθετο, είναι ισοδύναμη με την ερώτηση αν το x είναι μέλος του συνόλου COMPOSITE. Μπορεί να αποδειχθεί ότι COMPOSITE ∈ NP επιβεβαιώνοντας ότι ικανοποιεί τον παραπάνω ορισμό(αν αναγνωρίσουμε φυσικούς αριθμούς με την δυαδική αναπαράσταση).

Το COMPOSITE επίσης είναι στην P.^[46][47]

NP-πληρότητα

Υπάρχουν πολλοί ισοδύναμοι ορισμοί περιγραφής της NP-πληρότητας.

Έστω L μια γλώσσα επί ενός πεπερασμένου αλφαβήτου Σ.

Η L είναι NP-πλήρης αν, και μόνο αν, οι παρακάτω συνθήκες ικανοποιούνται:

L ∈ NP; και
Για κάθε L′ \in NP είναι πολυωνυμικού χρόνου-αναγώγιμη στην L (γραμμένη ως $L'\leq _{p}L$ ),όπου $L'\leq _{p}L$ αν και μόνο εάν, οι παρακάτω συνθήκες ικανοποιούνται:
1. Υπάρχει f : Σ* → Σ* ώστε για κάθε w επί του Σ* να έχουμε: $(w\in L'\Leftrightarrow f(w)\in L)$ ; και
2. υπάρχει μια μηχανή Τούρινγκ πολυωνυμικού χρόνου που τερματίζει με f(w) στην ταινία για κάθε είσοδο w.

Αναφορές

↑ ^1,0 ^1,1 R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
↑ Juris. «Gödel, von Neumann, and the P = NP problem» (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101–107. http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf.
↑ Cook, Stephen (1971). «The complexity of theorem proving procedures». Proceedings of the Third Annual ACM Symposium on Theory of Computing. σελίδες 151–158.
↑ Fortnow, Lance (2009). «The status of the P versus NP problem» (PDF). Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186. Αρχειοθετήθηκε από το πρωτότυπο στις 2011-02-24. https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf. Ανακτήθηκε στις 2015-05-17.
↑ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, σελίδα 270. Thomson Course Technology, 2006. Ορισμός 7.19 και Θεώρημα 7.20.
↑ William I. Gasarch (June 2002). «The P=?NP poll.» (PDF). SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. http://www.cs.umd.edu/~gasarch/papers/poll.pdf. Ανακτήθηκε στις 29 December 2008.
↑ William I. Gasarch. «The Second P=?NP poll» (PDF). SIGACT News 74. http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf.
↑ Scott Aaronson. "PHYS771 Lecture 6: P, NP, and Friends".. 27 August 2007. http://www.scottaaronson.com/democritus/lec6.html.
↑ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214.
↑ «David Eppstein. "Computational Complexity of Games and Puzzles"».
↑ Arvind, Vikraman; Kurur, Piyush P. (2006). «Graph isomorphism is in SPP». Information and Computation 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002.
↑ Schöning, Uwe. «Graph isomorphism is in the low hierarchy». Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science 1987: 114–124. doi:10.1007/bfb0039599.
↑ Schöning, Uwe (1988). «Graph isomorphism is in the low hierarchy». Journal of Computer and System Sciences 37: 312–323. doi:10.1016/0022-0000(88)90010-4.
↑ Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.
↑ Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
↑ Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley. Advances in linear and integer programminghttp://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps. Oxford Lecture Series in Mathematics and its Applications 4. New York: Oxford University Press. pp. 103–144. MR 1438311https://www.ams.org/mathscinet-getitem?mr=1438311. Postscript file at website of Gondziohttp://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps and at McMaster University website of Terlakyhttp://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz.
↑ T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431–442 (1975)
↑ S. Aaronson and A. Wigderson (2008). «Algebrization: A New Barrier in Complexity Theory». Proceedings of ACM STOC'2008, pp. 731–740. doi:10.1145/1374376.1374481. http://www.scottaaronson.com/papers/alg.pdf.
↑ Aaronson, Scott. «Is P Versus NP Formally Independent?» (PDF) .
↑ Ben-David, Shai; Halevi, Shai (1992). On the independence of P versus NP. Technical Report. 714. Technion. Αρχειοθετήθηκε από το πρωτότυπο στις 2015-03-09. https://web.archive.org/web/20150309042450/http://www.cs.technion.ac.il/%7Eshai/ph.ps.gz. Ανακτήθηκε στις 2015-05-25 .
↑ Rudich, Steven; Wigderson, Avi (2004), Computational Complexity Theory, IAS/Park City Mathematics Series, 10, American Mathematical Society, σελ. 75, ISBN 9780821886922, https://books.google.com/books?id=47GwSJfb1mQC&pg=PA75 .
↑ John Markoff (8 Οκτωβρίου 2009). «Prizes Aside, the P-NP Puzzler Has Consequences». The New York Times.
↑ Gerhard J. Woeginger. «The P-versus-NP page». Ανακτήθηκε στις 25 Μαΐου 2014.
↑ Markoff, John (16 August 2010). «Step 1: Post Elusive Proof. Step 2: Watch Fireworks.». The New York Times. http://www.nytimes.com/2010/08/17/science/17proof.html?_r=1. Ανακτήθηκε στις 20 September 2010.
↑ Polymath Project wiki. «Deolalikar's P vs NP paper».
↑ Science News, "Crowdsourcing peer review"
↑ Dick Lipton (12 Αυγούστου 2010). «Fatal Flaws in Deolalikar's Proof?».
↑ Dick Lipton (15 Σεπτεμβρίου 2010). «An Update on Vinay Deolalikar's Proof». Ανακτήθηκε στις 31 Δεκεμβρίου 2010.
↑ Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP
↑ Alexander Nazaryan (2 Μαΐου 2013). «A Most Profound Math Problem». Ανακτήθηκε στις 1 Μαΐου 2014.
↑ Elvira Mayordomo. "P versus NP" Αρχειοθετήθηκε 2012-02-16 στο Wayback Machine. Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).

Περαιτέρω Ανάγνωση

Fraenkel, Aviezri S.; Lichtenstein, David (1981). «Computing a perfect strategy for n×n chess requires time exponential in n». Automata, Languages and Programming 115: 278–293. doi:10.1007/3-540-10843-2_23.
Garey, Michael· Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. ISBN 0-7167-1045-5.
Goldreich, Oded (2010). P, Np, and Np-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Online drafts
Immerman, N. (1987). «Languages which capture complexity classes». SIAM Journal of Computing 16 (4): 760–778. doi:10.1137/0216051. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936.
Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 0-262-03293-7.
Παπαδημητρίου, Χρίστος (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 0-201-53082-1.
doi: 10.1145/1562164.1562186
Fortnow, L.· Gasarch, W. «Computational complexity».
Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible ISBN 9780691156491. Princeton University Press. Princeton, NJ (2013)

Εξωτερικοί σύνδεσμοι

The Clay Mathematics Institute Millennium Prize Problems
Gerhard J. Woeginger. The P-versus-NP page. Μια λίστα συνδέσμων σε μια σειρά από δήθεν λύσεις για το πρόβλημα. Ορισμένες από αυτές δηλώνουν ότι P=NP, ενώ μερικές από αυτά δηλώνουν το αντίθετο. Είναι πιθανό ότι όλες αυτές οι υποτιθέμενες λύσεις είναι εσφαλμένες.
Scott Aaronson 's Shtetl Optimized blog: Reasons to believe, μια λίστα αιτιολογήσεων ότι P ≠ NP

[Ladner75-1] 1,0 ^1,1 R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site.

[2] Juris. «Gödel, von Neumann, and the P = NP problem» (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101–107. http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf.

[3] Cook, Stephen (1971). «The complexity of theorem proving procedures». Proceedings of the Third Annual ACM Symposium on Theory of Computing. σελίδες 151–158.

[4] Fortnow, Lance (2009). «The status of the P versus NP problem» (PDF). Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186. Αρχειοθετήθηκε από το πρωτότυπο στις 2011-02-24. https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf. Ανακτήθηκε στις 2015-05-17.

[5] Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, σελίδα 270. Thomson Course Technology, 2006. Ορισμός 7.19 και Θεώρημα 7.20.

[poll-6] William I. Gasarch (June 2002). «The P=?NP poll.» (PDF). SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. http://www.cs.umd.edu/~gasarch/papers/poll.pdf. Ανακτήθηκε στις 29 December 2008.

[poll2-7] William I. Gasarch. «The Second P=?NP poll» (PDF). SIGACT News 74. http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf.

[8] Scott Aaronson. "PHYS771 Lecture 6: P, NP, and Friends".. 27 August 2007. http://www.scottaaronson.com/democritus/lec6.html.

[9] Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214.

[10] «David Eppstein. "Computational Complexity of Games and Puzzles"».

[AK06-11] Arvind, Vikraman; Kurur, Piyush P. (2006). «Graph isomorphism is in SPP». Information and Computation 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002.

[12] Schöning, Uwe. «Graph isomorphism is in the low hierarchy». Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science 1987: 114–124. doi:10.1007/bfb0039599.

[13] Schöning, Uwe (1988). «Graph isomorphism is in the low hierarchy». Journal of Computer and System Sciences 37: 312–323. doi:10.1016/0022-0000(88)90010-4.

[14] Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.

[Pisinger2003-15] Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

[16] Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley. Advances in linear and integer programminghttp://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps. Oxford Lecture Series in Mathematics and its Applications 4. New York: Oxford University Press. pp. 103–144. MR 1438311https://www.ams.org/mathscinet-getitem?mr=1438311. Postscript file at website of Gondziohttp://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps and at McMaster University website of Terlakyhttp://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz.

[17] T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431–442 (1975)

[18] S. Aaronson and A. Wigderson (2008). «Algebrization: A New Barrier in Complexity Theory». Proceedings of ACM STOC'2008, pp. 731–740. doi:10.1145/1374376.1374481. http://www.scottaaronson.com/papers/alg.pdf.

[19] Aaronson, Scott. «Is P Versus NP Formally Independent?» (PDF) .

[20] Ben-David, Shai; Halevi, Shai (1992). On the independence of P versus NP. Technical Report. 714. Technion. Αρχειοθετήθηκε από το πρωτότυπο στις 2015-03-09. https://web.archive.org/web/20150309042450/http://www.cs.technion.ac.il/%7Eshai/ph.ps.gz. Ανακτήθηκε στις 2015-05-25 .

[21] Rudich, Steven; Wigderson, Avi (2004), Computational Complexity Theory, IAS/Park City Mathematics Series, 10, American Mathematical Society, σελ. 75, ISBN 9780821886922, https://books.google.com/books?id=47GwSJfb1mQC&pg=PA75 .

[22] John Markoff (8 Οκτωβρίου 2009). «Prizes Aside, the P-NP Puzzler Has Consequences». The New York Times.

[23] Gerhard J. Woeginger. «The P-versus-NP page». Ανακτήθηκε στις 25 Μαΐου 2014.

[NYT2010-24] Markoff, John (16 August 2010). «Step 1: Post Elusive Proof. Step 2: Watch Fireworks.». The New York Times. http://www.nytimes.com/2010/08/17/science/17proof.html?_r=1. Ανακτήθηκε στις 20 September 2010.

[25] Polymath Project wiki. «Deolalikar's P vs NP paper».

[26] Science News, "Crowdsourcing peer review"

[27] Dick Lipton (12 Αυγούστου 2010). «Fatal Flaws in Deolalikar's Proof?».

[28] Dick Lipton (15 Σεπτεμβρίου 2010). «An Update on Vinay Deolalikar's Proof». Ανακτήθηκε στις 31 Δεκεμβρίου 2010.

[29] Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP

[30] Alexander Nazaryan (2 Μαΐου 2013). «A Most Profound Math Problem». Ανακτήθηκε στις 1 Μαΐου 2014.

[31] Elvira Mayordomo. "P versus NP" Αρχειοθετήθηκε 2012-02-16 στο Wayback Machine. Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]