Τι είναι το πρόβλημα της χιλιετίας;
Ερ: Τι είναι το πρόβλημα της χιλιετίας;
A: Το Πρόβλημα της Χιλιετίας είναι ένα από τα σημαντικότερα και πιο απαιτητικά μαθηματικά προβλήματα αυτού του αιώνα, το οποίο πραγματεύεται το ερώτημα αν κάθε πρόβλημα που είναι εύκολο να επαληθευτεί από τους υπολογιστές είναι επίσης εύκολο να λυθεί.
Ερ: Πώς μπορούμε να ταξινομήσουμε τα μαθηματικά προβλήματα;
Α: Τα μαθηματικά προβλήματα μπορούν να ταξινομηθούν ως προβλήματα P ή NP με βάση το αν είναι επιλύσιμα σε πεπερασμένο πολυωνυμικό χρόνο.
Ερ: Ποια είναι η διαφορά μεταξύ των προβλημάτων P και NP;
Α: Τα προβλήματα P είναι σχετικά γρήγορα και "εύκολα" για τους υπολογιστές να τα λύσουν, ενώ τα προβλήματα NP είναι γρήγορα και "εύκολα" για τους υπολογιστές να τα ελέγξουν, αλλά όχι απαραίτητα εύκολα να τα λύσουν.
Ερ: Ποιος εισήγαγε το πρόβλημα P έναντι του προβλήματος NP;
Α: Ο Stephen Cook εισήγαγε το πρόβλημα P έναντι NP το 1971 στο άρθρο του "The complexity of theorem proving procedures" (Η πολυπλοκότητα των διαδικασιών απόδειξης θεωρημάτων).
Ερ: Γιατί είναι σημαντικό το πρόβλημα P έναντι NP;
Α: Το πρόβλημα P versus NP θεωρείται το σημαντικότερο ανοιχτό πρόβλημα στην επιστήμη των υπολογιστών και είναι ένα από τα επτά προβλήματα του βραβείου Millennium, με βραβείο 1.000.000 δολαρίων για μια λύση που θα προσκαλέσει σε δημοσιευμένη αναγνώριση από το Ινστιτούτο Clay και πιθανώς μια ή περισσότερες λύσεις που θα αλλάξουν το σύνολο των μαθηματικών.
Ερώτηση: Είναι δυνατόν να λυθεί ένα NP-πλήρες πρόβλημα σε τετραγωνικό ή γραμμικό χρόνο;
Α: Το 1956, ο Kurt Gödel έγραψε μια επιστολή στον John von Neumann, στην οποία ρωτούσε αν ένα συγκεκριμένο NP-πλήρες πρόβλημα μπορεί να λυθεί σε τετραγωνικό ή γραμμικό χρόνο.
Ερ: Γιατί πολλοί μαθηματικοί ελπίζουν ότι τα Προβλήματα της Χιλιετίας συνδέονται μεταξύ τους;
Α: Πολλά από τα Προβλήματα της Χιλιετίας αγγίζουν συναφή ζητήματα, και είναι το όνειρο πολλών μαθηματικών να επινοήσουν ενοποιητικές θεωρίες.
