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

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

Теорія, що стосується проблем, які є NP-повноцінними.

ndigkeit

Досі залишається відкритим питання, чи відрізняються класи складності NP і P.

Взагалі, NP ≠ P-гіпотеза передбачається, оскільки дуже малоймовірні висновки можна зробити з припущення NP = P. Якщо NP ≠ P, то не може бути поліноміальних алгоритмів (поліноміальний алгоритм) для NP-повних та NP-жорстких задач (NP-жорстких задач). Для проблем у NP доказ повноти NP є з сьогоднішньої точки зору найсильнішим свідченням того, що проблема не міститься в P. Вперше в теоремі Кука (Cook, Theorem of) проблема виявилась NP-повною. Щоб довести NP-повноту задачі в NP, достатньо навести поліноміальне скорочення часу від NP-повної задачі до досліджуваної. Список важливих відомих проблем із повним NP містить кілька тисяч записів.

Теорія повноти NP є найважливішою галуззю теорії складності, також для додатків.