NP-úplný problém

Z Wikipédie

NP-úplný problém je taký problém (taká úloha), ktorej výpočtová zložitosť je väčšia, než polynomiálna. NP-úplné problémy napríklad sú:

  • Problém obchodného cestujúceho
  • Úloha, či daný graf možno zafarbiť tromi farbami
  • Kvadratická diofantická rovnica