NP-повна задача, будь-яка з класу обчислювальних задач, для яких не знайдено ефективного алгоритму вирішення. До цього класу належать багато важливих проблем інформатики, наприклад, проблема комівояжера, проблеми виконуваності та проблеми покриття графів.

Пояснення: Гамільтонова схема, bin упаковка, проблеми розбиття є повними проблемами NP.

NP-повні задачі

• Булева проблема виконуваності (SAT)
• Проблема ранця.
• Проблема гамільтонового шляху.
• Задача комівояжера (версія рішення)
• Проблема ізоморфізму підграфа.
• Проблема суми підмножини.
• Проблема кліків.
• Проблема покриття вершин.

Ми говоримо, що X є NP-повним, якщо: X ∈ NP • для всіх Y ∈ NP, Y ≤P X. Якщо вони виконуються, то X можна використовувати для вирішення будь-якої проблеми в NP. Тому X, безперечно, є принаймні такою ж складною, як і кожна проблема в NP.

Проблеми в NP, про які не відомо, що вони є в P або NP-complete Проблема ізоморфізму графа, проблема дискретного логарифмування та задача розкладання на множники цілих чисел є прикладами проблем, які вважаються проміжними NP. Це одні з небагатьох проблем NP, про які не відомо, що вони знаходяться в P або є NP-повними.

Проблема називається NP (недетермінований поліном), якщо її розв’язок можна вгадати та перевірити за поліноміальний час; недетермінований означає, що для припущення не дотримується жодного конкретного правила. Якщо проблема є NP і всі інші проблеми NP зводяться до неї за поліноміальним часом, проблема є NP-повною.

Задовільна схема, покриття вершин, проблеми з зупинкою тощо, є кількома прикладами NP-складних проблем. Декілька прикладів NP-Complete Problems – це визначення гамільтонового циклу на графіку, визначення рівня задоволення булевої формули тощо.