NP-úplný problém
Z Wikipédie
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 neho 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:
- Existencia Hamiltonovskej kružnice
- Úloha, či daný graf možno zafarbiť k farbami
- Kvadratická diofantická rovnica