Просмотр кода страницы NP-полная задача

[[Файл:P np np-complete np-hard.svg|thumb|400px|Взаимоотношение между классами P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если [[Равенство классов P и NP|P≠NP]] и если P=NP]]
'''NP-полная задача''' — в [[теория алгоритмов|теории алгоритмов]] [[Проблема разрешимости|задача с ответом «да» или «нет»]] из [[класс NP|класса NP]], к которой можно свести любую другую задачу из этого класса за [[полиномиальное время]] (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них будет найден «полиномиально быстрый» алгоритм решения, то и любую другую задачу из класса NP можно будет решить так же «быстро».

== Формальное определение ==
'''[[Алфавит (математика)|Алфавитом]]''' называется всякое конечное [[множество]] [[символ]]ов (например, {<math>{0,1}</math>} или {<math>{a,b,c}</math>}). Множество всех возможных '''[[слово (математика)|слов]]''' (конечных [[Строковый тип|строк]], составленных из символов этого алфавита) над некоторым алфавитом <math>\Sigma</math> обозначается <math>\Sigma^*</math>. '''[[Формальный язык|Языком]]''' <math>L</math> над алфавитом <math>\Sigma</math> называется всякое [[подмножество]] множества <math>\Sigma^*</math>, то есть <math>L\subset\Sigma^*</math>.

'''Задачей распознавания''' для языка <math>L</math> называется определение того, принадлежит ли данное слово языку <math>L</math>.

Пусть <math>L_1</math> и <math>L_2</math> — два языка над алфавитом <math>\Sigma</math>. Язык <math>L_1</math> называется [[Сведение по Карпу|сводимым (по Карпу)]] к языку <math>L_2</math>, если существует [[функция (математика)|функция]], <math>f\colon \Sigma^* \to \Sigma^*</math>, вычислимая за [[класс P|полиномиальное время]], обладающая следующим свойством:
* <math>x\in L_1 </math> тогда и только тогда, когда <math>f(x)\in L_2</math>. Сводимость по Карпу обозначается как <math>L_1 {\le}_p L_2</math> или <math>L_1 \varpropto L_2</math>.

Язык <math>L_2</math> называется '''{{якорь2|NP-hard|текст=NP-трудным}}''', если любой язык из класса NP сводится к нему. Язык называют '''NP-полным''', если он NP-труден, и при этом сам лежит в классе NP.

Неформально говоря, то что задача <math>A</math> сводится к задаче <math>B</math>, означает, что задача <math>A</math> «не сложнее» задачи <math>B</math> (так как, если мы можем решить <math>B</math>, то можем решить и <math>A</math>).
Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).

Из определения следует, что, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в [[класс P|классе P]], то есть будут решаться за полиномиальное время.

=== NP-полнота в сильном смысле ===
{{main|{{нп5|NP-полнота в сильном смысле|||Strong NP-completeness}}}}
Задача называется '''NP-полной в сильном смысле''', если у неё существует подзадача, которая:
# не является [[задача с числовыми параметрами|задачей с числовыми параметрами]] (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)
# является NP-полной.
Класс таких задач называется '''NPCS'''. Если [[Равенство классов P и NP|гипотеза P ≠ NP]] верна, то для NPCS-задачи не существует [[псевдополиномиальный алгоритм|псевдополиномиального алгоритма]]{{Нет АИ|12|07|2017}}.

== Гипотеза P ≠ NP ==
{{основная статья|Равенство классов P и NP}}
Вопрос о совпадении классов P и NP уже более пятидесяти лет является одной из центральных [[открытая проблема|открытых проблем]]. Научное сообщество склоняется к отрицательному ответу на этот вопрос<ref>{{статья |заглавие=The P=?NP poll. |издание=SIGACT News |том=33 |номер=2 |страницы=34—47 |ссылка=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |язык=und |автор=William I. Gasarch |год=2002 |archivedate=2007-06-15 |archiveurl=https://web.archive.org/web/20070615132837/http://www.cs.umd.edu/~gasarch/papers/poll.pdf }}</ref> — в этом случае решать NP-полные задачи за полиномиальное время не удастся.

== Примеры NP-полных задач ==
{{Main|{{нп5|Список NP-полных задач|Список NP-полных задач|en|List of NP-complete problems}}}}
{{кол}}
* [[Задача выполнимости булевых формул|Задача о выполнимости булевых формул]]
* [[Задача коммивояжёра]]
* [[Задача о вершинном покрытии]]
* [[Задача о покрытии множества]]
* [[Задача о независимом множестве]]
* [[Задача о клике]]
* [[Проблема Штейнера]]
* [[Раскраска графа|Проблема раскраски графа]]
* [[Игра в 15|Пятнашки]]
* [[Судоку]]
* [[Сапёр (игра)|Сапёр]]
* [[Тетрис]]<ref>Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. [http://arxiv.org/abs/cs.CC/0210020 Tetris is Hard, Even to Approximate]{{ref-en}}. preprint.</ref>
* [[Кубик-змейка]]<ref>{{Cite journal
|last1=Abel
|first1=Z.
|last2=Demaine
|first2=E.D.
|last3=Demaine
|first3=M.L.
|last4=Eisenstat
|first4=S.
|last5=Lynch
|first5=J.
|last6=Schardl
|first6=T.B.
|year=2013
|title=Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
|url=https://www.jstage.jst.go.jp/article/ipsjjip/21/3/21_368/_article
|journal=Journal of Information Processing
|volume=21
|issue=3
|pages=368–377
|access-date=2023-12-05
|archive-date=2023-12-05
|archive-url=https://web.archive.org/web/20231205122650/https://www.jstage.jst.go.jp/article/ipsjjip/21/3/21_368/_article
|url-status=live
}}</ref>
{{конец}}

== См. также ==
* [[Равенство классов P и NP]]

== Примечания ==
{{примечания}}

== Литература ==
* ''Гэри М., Джонсон Д.'' [http://trpl7.ru/t-books/NP-book126.pdf Вычислительные машины и труднорешаемые задачи] {{Wayback|url=http://trpl7.ru/t-books/NP-book126.pdf |date=20191104180723 }}. М.: Мир, 1982.
* {{книга
|автор = Томас Х. Кормен и др.
|часть = '''Глава 34. NP-полнота'''
|заглавие = Алгоритмы: построение и анализ
|оригинал = Introduction to Algorithms
|ссылка = 
|издание = 2-е изд
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страниц = 1296
|isbn = 0-07-013151-1
}}
* {{книга
|заглавие = Введение в теорию автоматов, языков и вычислений
|оригинал = Introduction to Automata Theory, Languages, and Computation
|автор = [[Джон Хопкрофт]], Раджив Мотвани, Джеффри Ульман
|ссылка = 
|isbn = 0-201-44124-1
|страниц = 528
|год = 2002
|издание = 
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}

== Ссылки ==
* [https://web.archive.org/web/20070616041921/http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/np-completeness-2004  NP-полнота]
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Вычислительная сложность игр и головоломок] {{Wayback|url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |date=20061206012118 }}{{ref-en}}
* [http://www.nada.kth.se/~viggo/problemlist/compendium.html A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann] {{Wayback|url=http://www.nada.kth.se/~viggo/problemlist/compendium.html |date=20061205232508 }}{{ref-en}}



{{Классы сложности}}
{{NP-полные задачи}}

[[Категория:NP-полные задачи|*]]