NP-Complete; ndigkeit - Lexikón matematiky

Lexikón matematiky: NP-úplnosť

Teória zaoberajúca sa problémami, ktoré sú NP-úplné.

lexikón

Stále zostáva otvorenou otázkou, či sú triedy zložitosti NP a P odlišné.

Všeobecne sa predpokladá hypotéza NP ≠ P, pretože z predpokladu NP = P možno odvodiť veľmi nepravdepodobné závery. Ak NP ≠ P, nemôžu existovať polynomické algoritmy (polynomiálny algoritmus) pre NP-úplné a NP-tvrdé problémy (NP-tvrdý problém). Pre problémy v NP je dôkaz úplnosti NP z dnešného pohľadu najsilnejšou známkou toho, že problém nie je obsiahnutý v P. Prvýkrát sa v Cookovej vete (Cook, Theorem of) problém ukázal ako NP-úplný. Na dokázanie NP-úplnosti problému v NP stačí dať skúmanému problému polynomiálnu redukciu času z NP-úplného problému. Zoznam dôležitých známych problémov NP-Complete obsahuje niekoľko tisíc položiek.

Teória úplnosti NP je najdôležitejšou vetvou teórie zložitosti, tiež pre aplikácie.