NP-úplný problém

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

NP-úplný problém je taký problém, ktorý patrí do NP (je vypočítateľný v nedeterministickom polynomiálnom čase) a ľubovoľný iný problém z NP je na naň deterministicky polynomiálne redukovateľný (tzn. je NP-ťažký). NP-úplné problémy v istom zmysle reprezentujú tie najťažšie spomedzi množiny NP. Pokiaľ by niekto našiel deterministický polynomiálny algoritmus pre ľubovoľný NP-úplný problém, vďaka existujúcej redukcii by boli všetky problémy z NP riešiteľné v polynomiálnom deterministickom čase (P=NP). Takýto algoritmus doposiaľ nebol nájdený a väčšina odborníkov sa prikláňa k názoru, že neexistuje.

NP-úplné problémy sú napríklad:


V teórii počítačovej zložitosti je trieda zložitosti NP-úplná taká trieda problémov ktorá má dve vlastnosti:

- Každé dané riešenie k problému môže byť overené rýchlo (v polynomickom čase); množina problémov s touto vlastnosťou sa nazýva NP (nedeterministický polynomický čas).
- Ak problém môže byť vyriešený rýchlo (v polynomickom čase), potom môže byť taký každý problém v NP.

Hoci každé dané riešenie k takému problému môže byť overené rýchlo, nie je známa efektívna cesta pre nájdenie riešenia na prvom mieste; samozrejme, najdôležitejšou charakteristikou NP-úplných problémov je že nie je známe žiadne rýchle riešenie. To znamená, že čas potrebný na riešenie problému pomocou ktoréhokoľvek v súčasnosti známeho algoritmu rastie veľmi rýchlo spolu s veľkosťou problému. Dôsledkom toho čas potrebný na vyriešenie aj stredne veľkých verzii takýchto 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. V dôsledku tohto je určovanie či je alebo nie je možné vyriešiť tieto problémy rýchlo jedným z hlavných nevyriešených problémov v počítačovej vede dneška.