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

Діаграма Венна відношення між класами складності задач (у випадку вірності гіпотези P ≠ NP).

NP-повна задача (Шаблон:Lang-en) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.

Формальне визначення

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

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

Якщо довільний окремий випадок задачі $L_1$ можна перетворити в деякий окремий випадок задачі $L_2$ в такий спосіб, що розв'язок задачі $L_1$ можна отримати за поліноміальний час від розв'язку задачі $L_2$ то кажуть, що $L_1$ зводиться до $L_2$.

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

NP-повнота в сильному сенсі

Задача називається NP-повною в сильному сенсі, якщо у неї існує підзадача, яка:

1. Не є задачею з числовими параметрами (тобто максимальне значення величин, що зустрічаються в цій задачі, обмежено зверху поліномом від довжини входу),
2. Належить до класу NP,
3. Є NP-повною.

Клас таких задач називається NPCS. Якщо гіпотеза P ≠ NP справедлива, то для NPCS задач не існує псевдополіноміального алгоритму.

Гіпотеза P ≠ NP

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

Приклади

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

Див. також

• Список класів складності
• Клас складності P

• NP-складна задача
• Комбінаторика
• Еволюційний алгоритм