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

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 00:54, 2 березня 2022, створена InternetArchiveBot (обговорення | внесок) (Bluelink 1 book for Перевірність (20220301)) #IABot (v2.0.8.6) (GreenC bot)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку
Діаграма Венна відношення між класами складності задач (у випадку вірності гіпотези P ≠ NP).

NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.[1]

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

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

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

Гіпотеза P ≠ NP

[ред. | ред. код]

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

Приклади

[ред. | ред. код]

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. а б Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.) . Москва: Мир. с. 442—443.
  2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2-ге). Addison-Wesley. с. 419. ISBN 0-201-44124-1.