Πρόβλημα P=NP

Το Πρόβλημα 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 πληρότητα

Για να προσεγγίσουμε το ερώτημα αν 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 "τρέχει" για χρόνο τουλάχιστον  για κάποια σταθερά c. Εδώ, n είναι το μήκος της δήλωσης Presburger. Έτσι, είναι γνωστό ότι το πρόβλημα χρειάζεται παραπάνω από εκθετικό χρόνο εκτέλεσης. Ακόμα πιο δύσκολα είναι τα μη αποφασίσιμα προβλήματα, όπως το πρόβλημα τερματισμού. Δεν μπορούν να επιλυθούν πλήρως από έναν αλγόριθμο, με την έννοια ότι για οποιονδήποτε συγκεκριμένο αλγόριθμο υπάρχει τουλάχιστον μία είσοδος για την οποία ο αλγόριθμος δεν θα παράγει το σωστό αποτέλεσμα. Είτε θα δώσει λάθος αποτέλεσμα , τελειώνοντας χωρίς να δώσει τελική απάντηση, είτε θα εκτελείται επ' άπειρον χωρίς να παράγει αποτέλεσμα.

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

Όλη η προηγούμενη συζήτηση έχει οδηγήσει στην υπόθεση πως P σημαίνει "εύκολο" και "όχι P" σημαίνει "δύσκολο",μία υπόθεση γνωστή ως θέση του Cobham. Είναι συνηθισμένη και λογικά ακριβής υπόθεση στην θεωρία πολυπλοκότητας. Ωστόσο, έχει κάποιους περιορισμούς.
Αρχικά, δεν είναι πάντα αληθής στην πράξη. Ένας θεωρητικός πολυωνυμικός αλγόριθμος μπορεί να έχει πολύ μεγάλους σταθερούς παράγοντες ή εκθετικούς καθιστώντας την ανέφικτη. Από την άλλη πλευρά, ακόμα κι αν ένα πρόβλημα αποδειχθεί να είναι NP-πλήρες, ακόμα κι αν P ≠NP, μπορεί να υπάρχουν αποδοτικές προσεγγίσεις για να αντιμετωπίσουμε το πρόβλημα στην πράξη. Υπάρχουν αλγόριθμοι για πολλά NP-πλήρη προβλήματα, όπως το πρόβλημα του σακιδίου, το πρόβλημα του περιπλανώμενου πωλητή και  το πρόβλημα ελέγχου ικανοποιησιμότητας λογικών εκφράσεων, που μπορούν να λύσουν στο βέλτιστο κάποια προβλήματα τη πραγματικότητας σε λογικό χρονικό διάστημα.  Η εμπειρική πολυπλοκότητα μέσου προβλήματος (χρόνος εναντίον μεγέθους προβλήματος) τέτοιων αλγορίθμων μπορεί να είναι εκπληκτικά μικρή. Ένα παράδειγμα είναι ο αλγόριθμος simplex στον γραμμικό προγραμματισμό, ο οποίος δουλεύει εκπληκτικά καλά στην πράξη. Παρόλο που έχει την χειρότερη περίπτωση πολυπλοκότητας χρόνου  εκθετικά, εκτελείται το ίδιο γρήγορα με τους καλύτερους αλγορίθμους πολυωνυμικού χρόνου.
Δεύτερον, υπάρχουν τύποι υπολογισμών που δεν υπακούν στο μοντέλο μηχανής Turing στο οποίο P και NP ορίζονται, όπως κβαντικοί υπολογισμοί και τυχαιοποιημένοι αλγόριθμοι.

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

Σύμφωνα με γκάλοπ,  πολλοί επιστήμονες της πληροφορικής πιστεύουν ότι P ≠ NP. Ένας λόγος-"κλειδί" για την πίστη αυτή είναι ότι μετά από δεκαετίες μελέτης αυτών των προβλημάτων, κανείς δεν μπόρεσε να βρει αλγόριθμο πολυωνυμικού χρόνου για περισσότερα από 3000 σημαντικά γνωστά NP-πλήρη προβλήματα (δείτε τη λίστα NP-πλήρεις  προβλημάτων). Αυτοί οι αλγόριθμοι αναζητήθηκαν πολύ πριν οριστεί η ιδέα της NP-πληρότητας (τα 21 NP-πλήρη προβλήματα του Karp, από τα πρώτα που βρέθηκαν, ήταν όλα γνωστά υπάρχοντα προβλήματα τον καιρό που αποδείχτηκε πως είναι NP-πλήρη). Επιπλέον, το αποτέλεσμα P = NP  θα υπονοούσε πολλά άλλα καταπληκτικά αποτελέσματα τα οποία τώρα θεωρούνται ψευδή,όπως NP = co-NP και P = PH.
Είναι επίσης διαισθητικά ισχυριζόμενο, ότι η ύπαρξη προβλημάτων τα οποία είναι δύσκολο να λυθούν, αλλά για τα οποία οι λύσεις είναι εύκολο να επιβεβαιωθούν, ταιριάζει με την εμπειρία της καθημερινότητας.
Αν P = NP, τότε ο κόσμος θα ήταν ένα εντελώς διαφορετικό μέρος από ότι συνήθως υποθέτουμε πως είναι.Δεν θα υπήρχε καμία ιδιαίτερη αξία στα "δημιουργικά                               άλματα", κανένα θεμελιώδες κενό στο να λύσεις το πρόβλημα και στο να αναγνωρίσεις την λύση αφού αυτή βρεθεί.
— Scott Aaronson, MIT
Από την άλλη μεριά, κάποιοι μελετητές πιστεύουν πως υπάρχει υπεραισιοδοξία στην πίστη πως P ≠ NP και ότι οι μελετητές θα πρέπει να αναζητήσουν αποδείξεις ότι P = NP. Για παράδειγμα, το 2002 παρουσιάστηκαν αυτές οι δηλώσεις:
Το κύριο επιχείρημα υπέρ του P ≠ NP είναι η έλλειψη θεμελιώδους εξέλιξης στην περιοχή των εξαντλητικών ερευνών. Αυτό είναι, κατά τη γνώμη μου, ένα πολύ αδύναμο                   επιχείρημα. Ο χώρος των αλγορίθμων είναι πολύ μεγάλος και είμαστε μόνο στην αρχή της εξερεύνησης του. [...] Η ανάλυση του τελευταίου θεωρήματος του Fermat                         δείχνει επίσης ότι πολύ απλές ερωτήσεις μπορούν να απαντηθούν μόνο από βαθιές θεωρίες.
—Moshe Y. Vardi, Rice University
Το να είσαι προσκολλημένος σε μία θεωρία δεν είναι καλός οδηγός στον σχεδιασμό έρευνας. Κάποιος θα πρέπει να δει και τις δυο κατευθύνσεις κάθε προβλήματος.                        Η προκατάληψη προκάλεσε σε πολλούς διάσημους μαθηματικούς αποτυχία στη λύση διάσημων προβλημάτων, των οποίων η λύση ήταν αντίθετη των προσδοκιών                        τους, παρόλο που ανέπτυξαν όσες μεθόδους χρειάζονταν.
—Anil Nerode, Cornell University

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

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

P = NP

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

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

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

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

Το πρόβλημα P = NP μπορεί να αναπροσαρμοστεί από την άποψη ότι μπορεί να εκφραστεί ως ορισμένες κατηγορίες λογικών δηλώσεων, ως αποτέλεσμα των εργασιών στην περιγραφική πολυπλοκότητα.
Θεωρείστε όλες τις γλώσσες πεπερασμένων δομών με σταθερή υπόγραφη, συμπεριαλβανόμενης μιας σχέσης γραμμικής τάξης. Τότε, όλες οι γλώσσες που ανήκουν στην κλάση P μπορούν να εκφραστούν στην λογική πρώτης τάξης με την πρόσθεση ενός κατάλληλου σημείου συνδιασμών(fixed-point combinator).
Με τον ίδιο τρόπο, η κλάση NP είναι το σύνολο όλων των γλωσσών που μπορεί να εκφραστεί σε υπαρξιακή λογική δεύτερης τάξης, Δηλαδή, η λογική δεύτερης τάξης περιορίζεται να αποκλείσει την καθολική ποσοτικοποίηση πάνω στις σχέσεις, τις λειτουργίες και τα υποσύνολα. Οι γλώσσες στην πολυώνυμο ιεραρχία  'PH' , αντιστοιχούν σε όλες τις λογικές δεύτερης τάξης. Έτσι, το ερώτημα "είναι  'P'  ένα κατάλληλο υποσύνολο του  'NP' » μπορεί να αναδιατυπωθεί ως «είναι η υπαρξιακή λογική δεύτερης τάξης σε θέση να περιγράψει τις γλώσσες (πεπερασμένων γραμμικά διατεταγμένων δομών με μη τετριμμένη υπογραφή) ότι η λογική πρώτης τάξης με τουλάχιστον σταθερό σημείο δεν μπορούν; »., .

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

Για κάθε 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 σε πολυωνυμικό χρόνο.