Πρόβλημα P=NP

Διάγραμμα των κλάσεων πληρότητας δεδομένου ότι P ≠ NP. Η ύπαρξη προβλημάτων εντός της κλάσης NP αλλά εκτός των P και NP-πλήρης, υπό αυτή την υπόθεση, καθιερώθηκε από το Θεώρημα Ladner.

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

Ουσιαστικά, αναφέρεται για πρώτη φορά σε μια επιστολή που γράφτηκε το 1956 από τον Κουρτ Γκέντελ στον Τζον φον Νόιμαν. Ο Γκέντελ ρώτησε αν ένα ορισμένο NP πλήρες πρόβλημα (το οποίο σημαίνει ότι μια οποιαδήποτε λύση μπορεί εύκολα να ελεγχθεί για το αν ικανοποιεί τις συνθήκες του προβλήματος) θα μπορούσε να λυθεί σε τετραγωνικό ή γραμμικό χρόνο. Η ακριβής δήλωση του προβλήματος P vs NP εισήχθη το 1971 από τον Στήβεν Κούκ στην δημοσίευσή του «Η πολυπλοκότητα θεωρημάτων αποδεικτικών διαδικασιών» και θεωρείται από πολλούς ως το πιο σημαντικό ανοικτό πρόβλημα στον τομέα αυτό. Πρόκειται για ένα από τα επτά προβλήματα του βραβείου Μιλλέννιουμ (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 αποτελείται από όλα τα προβλήματα απόφασης των οποίων οι λύσεις μπορούν να επιβεβαιωθούν σε πολυωνυμικό χρόνο με δεδομένο τις σωστές πληροφορίες, ή ισοδύναμα, των οποίων οι λύσεις μπορούν να βρεθούν σε πολυωνυμικό χρόνο σε μια μη-προσδιοριστή μηχανή. Είναι σαφές ότι, P ⊆ NP. Το μεγαλύτερο ανοικτό ερώτημα στην Θεωρητική Επιστήμη Υπολογιστών είναι η σχέση μεταξύ των δύο κλάσεων:

Ισχύει P = NP;

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

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

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 με εγγύηση ότι θα σταματήσει σε πολυωνυμικό χρόνο, υπάρχει ένα πολυωνυμικού μεγέθους δεδομένο εισόδου που θα αποδεχτεί η Μ; Είναι στην NP επειδή (αν δοθεί δεδομένο εισόδου) είναι απλό να ελεγχθεί αν η Μ δέχεται το δεδομένο εισόδου, προσομοιώνοντας την M. Είναι NP-πλήρες επειδή το μέσο επιβεβαίωσης για μια συγκεκριμένη περίπτωση ενός προβλήματος στην NP μπορεί να θεωρηθεί σαν μια πολυωνυμικού χρόνου μηχανή Μ, η οποία δέχεται την λύση σαν δεδομένο για να την επιβεβαιώσει. Τότε η ερώτηση αν η περίπτωση είναι "ναι ή όχι" περίπτωση, προσδιορίζεται από το αν υπάρχει έγκυρο δεδομένο εισόδου.

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

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

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

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

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

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

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

Το πρόβλημα παραγοντοποίησης ακεραίου είναι ένα υπολογιστικό πρόβλημα για τον προσδιορισμό των πρώτων παραγόντων ενός γνωστού ακεραίου. Εκφρασμένο ως ένα πρόβλημα απόφασης, είναι ένα πρόβλημα για την απόφαση εάν η είσοδος έχει παράγοντα μικρότερο από k. Δεν είναι γνωστός κάποιος αποδοτικός αλγόριθμος παραγοντοποίησης ακαιραίου και αυτή η βάση προκτύπτει από πολλά μοντέρνα συστήματα κρυπτογράφησης, όπως το RSA. Το πρόβλημα είναι της κλάσης NP και της co-NP). Άν το πρόβλημα είναι 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 = NP

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

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

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\}$

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

1. M τερματίζει για κάθε w και
2. υπάρχει $k\in N$ τέτοιο ώστε $T_{M}(n)\in O(n^{k})$, όπου O αναφέρεται στον ασυμπτωτικό συμβολισμό 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-πλήρης αν, και μόνο αν, οι παρακάτω συνθήκες ικανοποιούνται:

1. L ∈ NP; και
2. Για κάθε 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.

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

• 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