Перегляд вихідного коду сторінки NP-повна задача

[[Файл:Complexity classes.svg|thumb|right|[[Діаграма Венна]] відношення між класами складності задач (у випадку вірності гіпотези P ≠ NP).]]

'''NP-повна задача''' ({{lang-en|NP-complete}})&nbsp;— в [[теорія алгоритмів|теорії алгоритмів]] та [[Теорія складності обчислень|теорії складності]] це задача, що належить до [[клас складності NP|класу NP]] та всі задачі з класу NP можна [[Зведення (теорія складності обчислень)|звести]] до неї за поліноміальний час.<ref name="reingold">{{cite book|
title=Комбинаторные Алгоритмы|
author=Рейнгольд, Нивергельт Ю., Део Н.|
year=1980|
publisher=Мир|
pages=442—443|
мова=рос.|
place=Москва}}</ref>

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

Нехай <math>L</math>&nbsp;— мова (проблема) що належить до [[клас складності NP|класу NP]]. Мова <math>L</math> називається NP-повною якщо виконуються такі умови:
# <math>L</math> належить до NP.
# Для довільної мови <math>L'</math> в NP існує [[Зведення (теорія складності обчислень)|зведення]] до <math>L</math> за поліноміальний час.<ref name="hopcroft">{{cite book|
title=Introduction to Automata Theory, Languages and Computation| url=https://archive.org/details/introductiontoau00hopc_510|
author=John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman|
year=2001|
publisher=Addison-Wesley|
edition=2-ге| сторінки=[https://archive.org/details/introductiontoau00hopc_510/page/n432 419]|
мова=англ.|
isbn=0-201-44124-1}}</ref>

Якщо довільний окремий випадок задачі <math>L_1</math> можна перетворити в деякий окремий випадок задачі <math>L_2</math> в такий спосіб, що розв'язок задачі <math>L_1</math> можна отримати за поліноміальний час від розв'язку задачі <math>L_2</math> то кажуть, що <math>L_1</math> зводиться до <math>L_2</math>.<ref name="reingold"/>

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

=== NP-повнота в сильному сенсі ===
Задача називається '''NP-повною в сильному сенсі''', якщо у неї існує підзадача, яка:
# Не є [[задача з числовими параметрами|задачею з числовими параметрами]] (тобто максимальне значення величин, що зустрічаються в цій задачі, обмежено зверху поліномом від довжини входу),
# Належить до класу NP,
# Є NP-повною.
Клас таких задач називається '''[[NPCS]]'''. Якщо [[Рівність класів P і NP | гіпотеза P ≠ NP]] справедлива, то для NPCS задач не існує [[псевдополіноміальний алгоритм|псевдополіноміального алгоритму]].

== Гіпотеза P ≠ NP ==

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

== Приклади ==
{{Main|Список NP-повних задач}}
* [[Задача комівояжера]].
* [[Задача здійсненності бульових формул]].

== Див. також ==

{{multicol}}
* [[Список класів складності]]
* [[Клас складності P]]
{{multicol-break}}
* [[NP-складна задача]]
* [[Комбінаторика]]
* [[Еволюційний алгоритм]]
{{multicol-end}}

== Примітки ==
{{reflist}}
{{Портал|Математика}}
{{NP-повні задачі}}
{{Класи складності}}
{{Compu-prog-stub}}

[[Категорія:Класи складності]]
[[Категорія:Теорія складності обчислень]]
[[Категорія:Теорія алгоритмів]]