NP-повна задача
NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.[1]
Зміст |
Формальне визначення [ред.]
Нехай 
— мова (проблема) що належить до класу NP. Мова називається NP-повною якщо виконуються такі умови:
належить до NP.- Для довільної мови
в NP існує зведення до за поліноміальний час.[2]
в NP існує зведення до Якщо довільний окремий випадок задачі 
можна перетворити в деякий окремий випадок задачі 
в такий спосіб, що розв'язок задачі можна отримати за поліноміальний час від розв'язку задачі то кажуть, що зводиться до .[1]
Якщо P ≠ NP, то всі NP-повні проблеми знаходяться в множині NP — P, через це доведення NP-повноти задачі можна розглядати як додатковий аргумент на користь того, що проблема не належить до класу P і для неї не існує точного поліноміального алгоритму.
Гіпотеза P ≠ NP [ред.]
Рівність класів P і NP вже більше 30 років є відкритою проблемою. Наукове співтовариство схиляється до негативного вирішення цього питання — у цьому випадку за поліноміальний час вирішувати NP-повні задачі не вдасться.
Приклади [ред.]
Посилання [ред.]
- ↑ а б Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.). Москва: Мир. с. 442—443.
- ↑ 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.
