Vai atceraties, kas ir NP pilns uzdevums? Kā tas atšķiras no vienkārša NP?

NP (neatkarīgs polinomāla laika) — tas ir problēmu klases, kuras risinājumu var pārbaudīt polinomālā laikā. Citiem vārdiem, ja jums ir kandidāts uz atbildi, jūs to varat ātri pārbaudīt, vai tas ir pareizs vai nē.

NP pilnās problēmas ir NP apakškopa, kas vienlaikus ir "visgrūtākās" šajā klasē. Ja kāds atrastu polinomāla laika algoritmu jebkuras NP pilnās problēmas risināšanai, tad visas NP problēmas varētu tikt risinātas polinomālā laikā.

Galvenā atšķirība:

• NP — problēmas, kuru risinājumus var ātri pārbaudīt.
• NP pilnas — problēmas NP, uz kurām var samazināt jebkuru citu NP problēmu (t.i., tās ir "viskomplicētākās" NP).

Piemērs: maksimālās klikas problēma grafikā ir NP pilna, bet problēma pārbaudīt, vai elementu apakškopa ir vienāda ar dotu skaitli, ir NP klasē.