Ar prisimenate, kas yra NP pilnas uždavinys? Kaip jis skiriasi nuo paprasto NP?

NP (neapibrėžtas polinominiu laiku) — tai problemų klasė, kuriai sprendimą galima patikrinti per polinominiu laiką. Kitaip tariant, jei turite kandidatą į atsakymą, galite greitai patikrinti, ar jis teisingas ar ne.

NP pilni problemos yra NP pogrupis, kurie yra tuo pačiu metu ir "sudėtingiausi" šioje klasėje. Jei kas nors rastų polinominiu laiku veikiantį algoritmą bet kuriai NP pilnai problemai spręsti, tada visi NP problemos galėtų būti sprendžiamos per polinominiu laiką.

Pagrindinis skirtumas:

• NP — problemos, kurių sprendimus galima greitai patikrinti.
• NP pilni — problemos NP, į kurias galima sumažinti bet kurią kitą NP problemą (t.y., jos yra "sudėtingiausios" NP klasėje).

Pavyzdys: didžiausios klikos problema grafe yra NP pilna, o problema patikrinti, ar tam tikras elementų pogrupis turi sumą lygią duotam skaičiui, yra NP klasėje.