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

Формальне визначення
Узагальнити
Перспектива
Нехай — мова (проблема) що належить до класу NP. Мова називається NP-повною якщо виконуються такі умови:
Якщо довільний окремий випадок задачі можна перетворити в деякий окремий випадок задачі в такий спосіб, що розв'язок задачі можна отримати за поліноміальний час від розв'язку задачі то кажуть, що зводиться до .[1]
Якщо P ≠ NP, то всі NP-повні проблеми знаходяться в множині NP — P, через це доведення NP-повноти задачі можна розглядати як додатковий аргумент на користь того, що проблема не належить до класу P і для неї не існує точного поліноміального алгоритму.
NP-повнота в сильному сенсі
Задача називається NP-повною в сильному сенсі, якщо у неї існує підзадача, яка:
- Не є задачею з числовими параметрами (тобто максимальне значення величин, що зустрічаються в цій задачі, обмежено зверху поліномом від довжини входу),
- Належить до класу NP,
- Є NP-повною.
Клас таких задач називається NPCS. Якщо гіпотеза P ≠ NP справедлива, то для NPCS задач не існує псевдополіноміального алгоритму.
Remove ads
Гіпотеза P ≠ NP
Рівність класів P і NP вже понад 30 років є відкритою проблемою. Наукове співтовариство схиляється до негативного вирішення цього питання — у цьому випадку за поліноміальний час вирішувати NP-повні задачі не вдасться.
Приклади
Див. також
|
Примітки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads