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

Нехай ${\displaystyle L}$ — мова (проблема) що належить до класу NP. Мова ${\displaystyle L}$ називається NP-повною якщо виконуються такі умови:

1. ${\displaystyle L}$ належить до NP.
2. Для довільної мови ${\displaystyle L'}$ в NP існує зведення до ${\displaystyle L}$ за поліноміальний час.[2]

Якщо довільний окремий випадок задачі ${\displaystyle L_{1}}$ можна перетворити в деякий окремий випадок задачі ${\displaystyle L_{2}}$ в такий спосіб, що розв'язок задачі ${\displaystyle L_{1}}$ можна отримати за поліноміальний час від розв'язку задачі ${\displaystyle L_{2}}$ то кажуть, що ${\displaystyle L_{1}}$ зводиться до ${\displaystyle L_{2}}$.[1]

Якщо P ≠ NP, то всі NP-повні проблеми знаходяться в множині NP — P, через це доведення NP-повноти задачі можна розглядати як додатковий аргумент на користь того, що проблема не належить до класу P і для неї не існує точного поліноміального алгоритму.

Рівність класів P і NP вже понад 30 років є відкритою проблемою. Наукове співтовариство схиляється до негативного вирішення цього питання — у цьому випадку за поліноміальний час вирішувати NP-повні задачі не вдасться.

• Задача комівояжера.
• Задача здійсненності бульових формул.