Θυμάστε τι είναι ένα πρόβλημα NP-πλήρους; Πώς διαφέρει από απλά NP;

NP (μη καθοριστικό πολυωνυμικό χρόνο) — είναι μια κατηγορία προβλημάτων για τα οποία η λύση μπορεί να ελεγχθεί σε πολυωνυμικό χρόνο. Δηλαδή, αν έχετε έναν υποψήφιο για απάντηση, μπορείτε γρήγορα να ελέγξετε αν είναι σωστός ή όχι.

Τα NP-πλήρη προβλήματα αποτελούν ένα υποσύνολο του NP που είναι ταυτόχρονα τα "πιο δύσκολα" σε αυτήν την κατηγορία. Αν κάποιος βρει έναν πολυωνυμικό αλγόριθμο για την επίλυση οποιουδήποτε NP-πλήρους προβλήματος, τότε όλα τα προβλήματα στο NP μπορούν να λυθούν σε πολυωνυμικό χρόνο.

Βασική διαφορά:

• NP — προβλήματα των οποίων οι λύσεις μπορούν να ελεγχθούν γρήγορα.
• NP-πλήρη — προβλήματα στο NP στα οποία μπορεί να μειωθεί οποιοδήποτε άλλο πρόβλημα NP (δηλαδή, είναι τα "πιο πολύπλοκα" στο NP).

Παράδειγμα: το πρόβλημα της μέγιστης κλικ σε ένα γράφο είναι NP-πλήρες, και το πρόβλημα ελέγχου αν ένα υποσύνολο στοιχείων αθροίζει σε έναν δοσμένο αριθμό ανήκει στο NP.