NP-úplný problém

NP-úplný problém je taký problém, ktorý patrí do triedy NP (je vypočítateľný v nedeterministickom polynomiálnom čase) a ľubovoľný iný problém z triedy NP je naň polynomiálne redukovateľný (tzn. je NP-ťažký). NP-úplné problémy v istom zmysle reprezentujú tie najťažšie problémy spomedzi triedy NP. Pokiaľ by niekto našiel deterministický polynomiálny algoritmus pre jeden NP-úplný problém, vďaka existujúcej redukcii by boli všetky problémy z triedy NP riešiteľné v deterministickom polynomiálnom čase (P=NP).

Častou chybou je interpretácia skratky NP v názve NP-úplný ako nepolynomiálny (ang. non-polynomial), t. j., neriešiteľný v deterministickom polynomiálnom čase. Aj keď sa väčšina odborníkov prikláňa k názoru, že neexistuje deterministický polynomiálny algoritmus pre žiadny NP-úplný problém, toto nebolo nikdy dokázané. Tiež treba dodať, že trieda NP obsahuje všetky problémy ktoré sú riešiteľné v deterministickom polynomiálnom čase.

NP-úplné problémy sú tiež charakteristické tým, že správnosť ich riešenia môže byť overená rýchlo (v deterministickom polynomiálnom čase), ale nie je známa efektívna cesta pre nájdenie riešenia. To znamená, že čas potrebný na riešenie NP-úplného problému rastie asymptoticky rýchlejšie ako polynomiálne (obvykle exponenciálne) vzhľadom na veľkosť zadania (inštancie) problému. Dôsledkom je, že čas potrebný na riešenie aj stredne veľkých inštancií NP-úplných problémov ľahko dosahuje bilióny alebo trilióny rokov pri použití akéhokoľvek množstva dnes dostupného výpočtového výkonu. Aj preto je otázka, či je možné riešiť NP-úplné problémy efektívne jednou z centrálnych otázok počítačovej vedy dneška.

Príklady NP-úplných problémov

• SATISFIABILITY, teda problém splniteľnosti výrokovej formule v konjunktívnej normálnej forme
• 3-SATISFIABILITY, teda problém splniteľnosti výrokovej formule v konjunktívnej normálnej forme, pričom každá klauzula obsahuje najviac tri literály
• Existencia Hamiltonovskej kružnice
• Úloha, či daný graf možno zafarbiť k farbami
• Kvadratická diofantická rovnica