НП-комплетен; ndigkeit - Лексикон за математика

Лексикон по математика: НП-комплетност

Теорија која се занимава со проблеми што се НП-комплетни.

Сè уште е отворено прашање дали класи на сложеност НП и Р се различни.

Општо, се претпоставува хипотезата за НП ≠ П, бидејќи многу неверојатно заклучоци можат да се изведат од претпоставката НП = П. Ако NP ≠ P, не може да има полиномски алгоритми (полиномски алгоритам) за NP-завршени и NP-тврди проблеми (NP-тврд проблем). За проблемите во НП, доказот за комплетноста на НП е од денешна перспектива најсилната индикација дека проблемот не е содржан во П. За прв пат во теоремата на Кук (Кук, теорема на) се покажа дека еден проблем е комплетен НП. За да се докаже комплетноста на НП на проблем во НП, доволно е да се даде намалување на полиномот од времето на целосниот проблем на НП на истражениот проблем. Списокот на важни познати проблеми со комплетни НП содржи неколку илјади записи.

Теоријата за комплетност на НП е најважната гранка на теоријата на сложеност, исто така за апликации.

---