(визначення) Визначення: The
задач вирішення, правильність відповідей яких можна перевірити, отримавши сертифікат, за допомогою алгоритму, час виконання якого поліноміальний за розміром вхідних даних (тобто це NP), і жодна інша проблема NP не є складнішою за поліноміальний фактор .
У теорії складності обчислень проблема є NP-повною, коли: Це проблема прийняття рішення, що означає, що для будь-якого входу в проблему результатом буде «так» або «ні».. Коли відповідь «так», це можна продемонструвати через існування короткого (поліноміальної довжини) рішення.
Якщо проблема є NP-повною, це означає, що багато великих математиків, комп'ютерників і дуже розумних розробників програмного забезпечення не змогли знайти ефективне вирішення проблеми. А це означає, що ніхто не може звинувачувати вас, якщо ви не можете його знайти.
NP-повна задача, будь-яка з класу обчислювальних задач, для яких не знайдено ефективного алгоритму вирішення. До цього класу належать багато важливих проблем інформатики, наприклад, проблема комівояжера, проблеми виконуваності та проблеми покриття графів.
Будь-яка задана проблема X діє як NP-Hard, лише якщо існує проблема Y, яка є NP-Complete. Тут проблема Y стає зведеною до проблеми X за поліноміальний час. Жорсткість NP-складної задачі еквівалентна складності NP-повної проблеми. Але тут NP-складні задачі не обов’язково повинні бути в класі NP.
- Теорема: якщо будь-яка NP-повна мова є в P, тоді P = NP.Доведення: якщо L ∈ NPC і L ∈ P, ми знаємо для будь-якого L' ∈ NP, що.
- Теорема: якщо будь-яка NP-повна мова не є в P, тоді P ≠ NP. Доведення: якщо L ∈ NPC, то L ∈ NP. Отже, якщо L ∉ P, то L ∈ NP – P.
- ● Якщо будь-яка проблема NPC знаходиться в P, тоді P = NP. ●