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).
čítajte viac o NP-úplný problém
Encyklopédia: Electronics.sk > Elektronika > >
Príbuzné výrazy:
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.