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