NP-Complete; ndigkeit - Лексикон на математиката

Лексикон на математиката: NP-пълнота

Теория, занимаваща се с проблеми, които са NP-пълни.

математиката

Все още остава открит въпросът дали класовете на сложност NP и P са различни.

Като цяло се приема хипотезата NP ≠ P, тъй като от предположението NP = P. могат да се извлекат много невероятни заключения Ако NP ≠ P, не може да има полиномиални алгоритми (полиномиален алгоритъм) за NP-пълни и NP-твърди задачи (NP-твърд проблем). За проблемите в NP доказателството за NP-пълнота е от днешна гледна точка най-силната индикация, че проблемът не се съдържа в P. За първи път в теоремата на Кук (Cook, Theorem of) проблемът е доказан като NP-пълен. За да се докаже NP-пълнотата на даден проблем в NP, е достатъчно да се даде полиномиално намаляване на времето от NP-пълен проблем до разглеждания проблем. Списъкът с важни известни проблеми, пълни с NP, съдържа няколко хиляди записа.

Теорията за пълнота на NP е най-важният клон на теорията на сложността, също и за приложения.