Emlékszik, mi az NP-teljes feladat? Miben különbözik az egyszerű NP-től?

NP (nem-determinisztikus polinom idő) — ez egy problémacsoport, amelyhez tartozó megoldás polinom idő alatt ellenőrizhető. Vagyis, ha van egy válaszjelölted, gyorsan ellenőrizheted, helyes-e vagy sem.

Az NP-teljes problémák az NP egy részhalmazát képezik, amelyek egyben a leg"nehezebb" problémák ebben a csoportban. Ha valaki találna egy polinom időben futó algoritmust bármely NP-teljes probléma megoldására, akkor az összes NP problémát polinom idő alatt lehetne megoldani.

Fő különbség:

• NP — problémák, amelyek megoldásait gyorsan ellenőrizni lehet.
• NP-teljes — NP problémák, amelyekre bármely más NP probléma redukálható (vagyis a leg"bonyolultabb" NP problémák).

Példa: a maximális klikk problémája gráfban NP-teljes, míg az összegző halmaz kérdése, hogy egy halmaz elemeinek összege egy adott számnak felel-e meg, NP-ben van.