Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων

 

== Πολυπλοκότητα ==

Παρόλο που κάποια προβλήματα είναι επιλύσιμα, δεν έχει βρεθεί μέχρι στιγμής αλγόριθμος που να τα επιλύει σε λογικά χρονικά όρια· δηλαδή με πολυωνυμική και όχι εκθετική χρονική πολυπλοκότητα. Σε αυτό το σημείο συνεισφέρει η θεωρία πολυπλοκότητας: P ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε πολυωνυμικό χρόνο. NP ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή μη ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε πολυωνυμικό χρόνο αλλά όχι ντετερμινιστική (οι ισοδύναμες ντετερμινιστικές Μηχανές Τούρινγκ έχουν αυξημένη εκθετική πολυπλοκότητα). E ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή είτε μη ντετερμινιστική είτε ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε εκθετικό χρόνο. Αυτή τη στιγμή γνωρίζουμε ότι το P είναι υποσύνολο του NP και ότι το NP είναι υποσύνολο του Ε. Ωστόσο δεν γνωρίζουμε κατά πόσον αυτές οι σχέσεις είναι γνήσιου υποσυνόλου, αν και υποψιαζόμαστε ότι αυτό ισχύει. Αν αποδειχτεί ότι το P δεν είναι γνήσιο υποσύνολο του NP τότε σημαίνει ότι υπάρχουν ντετερμινιστικές Μηχανές Τούρινγκ που επιλύουν όλα τα προβλήματα του NP σε πολυωνυμικό χρόνο και απλώς δεν έχουν επινοηθεί μέχρι στιγμής. Σήμερα ωστόσο αυτό δεν θεωρείται πιθανό και οι περισσότεροι επιστήμονες εικάζουν ότι η εκθετική πολυπλοκότητα είναι εγγενής σε αυτά τα προβλήματα.