NP-hardness
Ένα NP-δύσκολο πρόβλημα είναι ένα πρόβλημα ναι/όχι στο οποίο η εύρεση λύσης είναι τουλάχιστον τόσο δύσκολη όσο η εύρεση λύσης για το δυσκολότερο πρόβλημα του οποίου η λύση μπορεί να ελεγχθεί γρήγορα ως αληθής. Ορισμένα NP-hard προβλήματα είναι προβλήματα στα οποία μια λειτουργική λύση μπορεί να ελεγχθεί γρήγορα (NP προβλήματα) και ορισμένα όχι. Τα NP-hard προβλήματα που είναι επίσης NP προβλήματα εντάσσονται σε μια κατηγορία που ονομάζεται NP-complete.
Ένα παράδειγμα ενός προβλήματος που είναι τουλάχιστον τόσο δύσκολο να λυθεί όσο οποιοδήποτε άλλο πρόβλημα για το οποίο μπορούμε να ελέγξουμε γρήγορα τις λύσεις, το οποίο είναι επίσης γρήγορα ελέγξιμο (είναι τόσο NP-hard όσο και NP):
Ένας πλανόδιος πωλητής θέλει να επισκεφθεί 100 πόλεις οδικώς, ξεκινώντας και τελειώνοντας το ταξίδι του στο σπίτι του. Έχει περιορισμένο απόθεμα βενζίνης, οπότε μπορεί να διανύσει συνολικά μόνο 10.000 χιλιόμετρα. Θέλει να μάθει αν μπορεί να επισκεφθεί όλες τις πόλεις χωρίς να ξεμείνει από βενζίνη.
Οι άνθρωποι δεν ξέρουν πώς να λύσουν αυτό το πρόβλημα γρηγορότερα από το να δοκιμάσουν κάθε πιθανή απάντηση, αλλά αν βρεθεί μια λύση που επιτρέπει στον πωλητή να το κάνει αυτό, μπορούμε να χρησιμοποιήσουμε έναν αλγόριθμο για να ελέγξουμε ότι είναι αληθής. Το πρόβλημα αυτό είναι επίσης γνωστό ως πρόβλημα του πλανόδιου πωλητή.
Ένα παράδειγμα ενός προβλήματος που είναι τουλάχιστον τόσο δύσκολο να λυθεί όσο οποιοδήποτε άλλο πρόβλημα για το οποίο μπορούμε να ελέγξουμε γρήγορα τις λύσεις, αλλά το οποίο δεν μπορεί να ελεγχθεί γρήγορα (είναι NP-σκληρό, αλλά δεν είναι NP):
αν κάποιος ξεκινήσει ένα πρόγραμμα που απλά πηγαίνει,
while(true){ continue; }και δεν το σταματάει ποτέ, θα τρέχει για πάντα;
Δεν υπάρχει γνωστός τρόπος να βρεθεί λύση σε όλα τα προβλήματα αυτού του είδους, και αυτό επίσης δεν μπορεί να ελεγχθεί.
Ερωτήσεις και απαντήσεις
Ερ: Τι είναι ένα NP-δύσκολο πρόβλημα;
A: Ένα NP-δύσκολο πρόβλημα είναι ένας τύπος μαθηματικού προβλήματος που χρησιμοποιείται στην επιστήμη των υπολογιστών και είναι ένα πρόβλημα ναι/όχι, όπου η εύρεση λύσης για αυτό είναι τουλάχιστον τόσο δύσκολη όσο η εύρεση λύσης για το δυσκολότερο πρόβλημα του οποίου η λύση μπορεί γρήγορα να ελεγχθεί ως αληθής.
Ερώτηση: Μπορεί να ελεγχθεί γρήγορα μια λειτουργική λύση για όλα τα NP-δύσκολα προβλήματα;
Α: Όχι, μόνο ορισμένα NP-σκληρά προβλήματα, που ονομάζονται NP προβλήματα, έχουν λύσεις που μπορούν να ελεγχθούν γρήγορα.
Ερ: Πώς ονομάζεται η κατηγορία για τα NP-hard προβλήματα που είναι επίσης NP προβλήματα;
Α: Τα NP-δύσκολα προβλήματα που είναι επίσης NP προβλήματα εντάσσονται σε μια κατηγορία που ονομάζεται NP-πλήρη.
Ερ: Είναι όλα τα NP-δύσκολα προβλήματα NP-πλήρη;
Α: Όχι, δεν είναι όλα τα NP-δύσκολα προβλήματα NP-πλήρη. Μόνο αυτά που είναι επίσης προβλήματα NP εμπίπτουν σε αυτή την κατηγορία.
Ερ: Είναι εύκολο να λυθούν τα NP-δύσκολα προβλήματα;
Α: Όχι, τα NP-δύσκολα προβλήματα δεν είναι εύκολο να λυθούν. Στην πραγματικότητα, η εύρεση λύσης γι' αυτά είναι τουλάχιστον εξίσου δύσκολη με την εύρεση λύσης για το δυσκολότερο πρόβλημα του οποίου η λύση μπορεί να ελεγχθεί γρήγορα ως αληθής.
Ερ: Υπάρχουν οφέλη από την επίλυση NP-δύσκολων προβλημάτων;
Α: Ναι, η επίλυση ΝΡ-σκληρών προβλημάτων μπορεί να προσφέρει πλεονεκτήματα σε διάφορους τομείς, όπως η επιστήμη των υπολογιστών, η φυσική και οι κοινωνικές επιστήμες, καθώς μπορεί να απαιτούν πολύπλοκους υπολογισμούς και μοντελοποίηση.
Ερ: Υπάρχει συνεχής έρευνα για την επίλυση ΝΡ-δύσκολων προβλημάτων;
Α: Ναι, η έρευνα για την επίλυση ΝΡ-δύσκολων προβλημάτων συνεχίζεται, καθώς τα προβλήματα αυτά εξακολουθούν να είναι σημαντικά σε διάφορους τομείς και η εύρεση αποτελεσματικών αλγορίθμων και λύσεων μπορεί να έχει σημαντικές επιπτώσεις.
