NP-полная задача: различия между версиями

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 23:43, 4 августа 2024

NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них будет найден «полиномиально быстрый» алгоритм решения, то и любую другую задачу из класса NP можно будет решить так же «быстро».

Формальное определение

Алфавитом называется всякое конечное множество символов (например, { ${0,1}$ } или { ${a,b,c}$ }). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом $\Sigma$ обозначается $\Sigma ^{*}$ . Языком $L$ над алфавитом $\Sigma$ называется всякое подмножество множества $\Sigma ^{*}$ , то есть $L\subset \Sigma ^{*}$ .

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

Пусть $L_{1}$ и $L_{2}$ — два языка над алфавитом $\Sigma$ . Язык $L_{1}$ называется сводимым (по Карпу) к языку $L_{2}$ , если существует функция, $f\colon \Sigma ^{*}\to \Sigma ^{*}$ , вычислимая за полиномиальное время, обладающая следующим свойством:

$x\in L_{1}$ тогда и только тогда, когда $f(x)\in L_{2}$ . Сводимость по Карпу обозначается как $L_{1}{\leq }_{p}L_{2}$ или $L_{1}\varpropto L_{2}$ .

Язык $L_{2}$ называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.

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

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

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

Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая:

не является задачей с числовыми параметрами (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)
является NP-полной.

Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS-задачи не существует псевдополиномиального алгоритма^{[источник не указан 2708 дней]}.

Гипотеза P ≠ NP

Вопрос о совпадении классов P и NP уже более пятидесяти лет является одной из центральных открытых проблем. Научное сообщество склоняется к отрицательному ответу на этот вопрос^[1] — в этом случае решать NP-полные задачи за полиномиальное время не удастся.

Примеры NP-полных задач

См. также

Равенство классов P и NP

Примечания

↑ William I. Gasarch. The P=?NP poll. (неопр.) // SIGACT News. — 2002. — Т. 33, № 2. — С. 34—47. — doi:10.1145/1052796.1052804. Архивировано 15 июня 2007 года.
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate (англ.). preprint.
↑ Abel, Z.; Demaine, E.D.; Demaine, M.L.; Eisenstat, S.; Lynch, J.; Schardl, T.B. (2013). "Finding a Hamiltonian Path in a Cube with Specified Turns is Hard". Journal of Information Processing. 21 (3): 368—377. Архивировано 5 декабря 2023. Дата обращения: 5 декабря 2023.

Литература

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи Архивная копия от 4 ноября 2019 на Wayback Machine. М.: Мир, 1982.
Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — 1296 с. — ISBN 0-07-013151-1.
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.

Ссылки

NP-полнота
Вычислительная сложность игр и головоломок Архивная копия от 6 декабря 2006 на Wayback Machine (англ.)
A compendium of NP optimization problems. Editors — Pierluigi Crescenzi, Viggo Kann Архивная копия от 5 декабря 2006 на Wayback Machine (англ.)

[1] William I. Gasarch. The P=?NP poll. (неопр.) // SIGACT News. — 2002. — Т. 33, № 2. — С. 34—47. — doi:10.1145/1052796.1052804. Архивировано 15 июня 2007 года.

[2] Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate (англ.). preprint.

[3] Abel, Z.; Demaine, E.D.; Demaine, M.L.; Eisenstat, S.; Lynch, J.; Schardl, T.B. (2013). "Finding a Hamiltonian Path in a Cube with Specified Turns is Hard". Journal of Information Processing. 21 (3): 368—377. Архивировано 5 декабря 2023. Дата обращения: 5 декабря 2023.

[1]

[2]

[3]

@@ Строка 1: / Строка 1: @@
+[[Файл: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; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса 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>{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: \Sigma^* \to \Sigma^*</math>, вычислимая за [[класс P|полиномиальное время]], обладающая следующим свойством:
+Пусть <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>f(x)\in L_2</math> тогда и только тогда, когда <math>x\in L_1.</math>
+* <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_1 {\le}_p L_2</math> или <math>L_1 \varpropto L_2</math>.
-Язык <math>L_2</math> называется '''NP-трудным''', если любой язык из класса NP сводится к нему. Язык называют '''NP-полным''', если он NP-труден, и при этом сам лежит в классе NP.
+Язык <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-задачи окажутся в [[класс P|классе P]], то есть будут решаться за полиномиальное время.
+Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи, которые «сложнее» их (то есть те задачи, к которым могут быть сведены NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче» их (то есть те задачи, которые сводятся к NP-полным задачам).
+Из определения следует, что, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в [[класс P|классе P]], то есть будут решаться за полиномиальное время.
 === NP-полнота в сильном смысле ===
+{{main|{{нп5|NP-полнота в сильном смысле|||Strong NP-completeness}}}}
 Задача называется '''NP-полной в сильном смысле''', если у неё существует подзадача, которая:
-# не является [[задача с числовыми параметрами|задачей с числовыми параметрами]] (т.е. максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа),
+# не является [[задача с числовыми параметрами|задачей с числовыми параметрами]] (то есть максимальное значение величин, встречающихся в этой задаче, ограничено сверху полиномом от длины входа)
-# принадлежит классу NP,
 # является NP-полной.
-Класс таких задач называется '''NPCS'''. Если [[Равенство классов P и NP|гипотеза P ≠ NP]] верна, то для NPCS задачи не существует [[псевдополиномиальный алгоритм|псевдополиномиального алгоритма]].
+Класс таких задач называется '''NPCS'''. Если [[Равенство классов P и NP|гипотеза P ≠ NP]] верна, то для NPCS-задачи не существует [[псевдополиномиальный алгоритм|псевдополиномиального алгоритма]]{{Нет АИ|12|07|2017}}.
 == Гипотеза P ≠ NP ==
 {{основная статья|Равенство классов P и NP}}
-Вопрос о совпадении классов P и NP уже более 30 лет является [[открытая проблема|открытой проблемой]]. Научное сообщество склоняется к отрицательному ответу на этот вопрос<ref>{{cite journal|author=William I. Gasarch|title=The P=?NP poll.|journal=SIGACT News |volume=33 |issue=2 |pages=34–47 |year=2002 |url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804}}</ref> — в этом случае решать 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}}}}
+{{кол}}
 * [[Задача выполнимости булевых формул|Задача о выполнимости булевых формул]]
-* [[Пятнашки|Кратчайшее решение «пятнашек» размера <math>n\times n</math>]]
 * [[Задача коммивояжёра]]
-* [[Проблема Штейнера]]
-* [[Раскраска графа|Проблема раскраски графа]]
 * [[Задача о вершинном покрытии]]
 * [[Задача о покрытии множества]]
-* [[Задача о клике]]
 * [[Задача о независимом множестве]]
-* [[Сапер (игра)]]
+* [[Задача о клике]]
+* [[Проблема Штейнера]]
+* [[Раскраска графа|Проблема раскраски графа]]
+* [[Игра в 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]]
-* {{не переведено 3|Список NP-полных задач|Список NP-полных задач|en|List of NP-complete problems}}
 == Примечания ==
@@ Строка 46: / Строка 77: @@
 == Литература ==
+* ''Гэри М., Джонсон Д.'' [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
+|оригинал = Introduction to Algorithms
 |ссылка =
 |издание = 2-е изд
@@ Строка 56: / Строка 88: @@
 |издательство = [[Вильямс (издательство)|«Вильямс»]]
 |год = 2006
-|страницы = 1296
+|страниц = 1296
 |isbn = 0-07-013151-1
+}}
+* {{книга
+|заглавие = Введение в теорию автоматов, языков и вычислений
+|оригинал = Introduction to Automata Theory, Languages, and Computation
+|автор = [[Джон Хопкрофт]], Раджив Мотвани, Джеффри Ульман
+|ссылка =
+|isbn = 0-201-44124-1
+|страниц = 528
+|год = 2002
+|издание =
+|место =  М.
+|издательство = [[Вильямс (издательство)|«Вильямс»]]
 }}
 == Ссылки ==
-* [http://rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/np-completeness-2004  NP-полнота]
+* [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 Вычислительная сложность игр и головоломок]{{ref-en}}
+* [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]{{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}}
-{{info-stub}}

Классы сложности алгоритмов
Считаются лёгкими	DLOGTIME^[англ.] AC⁰^[англ.] ACC⁰^[англ.] TC⁰^[англ.] L SL^[англ.] RL^[англ.] NL NC SC^[англ.] CC^[англ.] P P-complete^[англ.] ZPP RP BPP BQP EQP APX
Предполагаются сложными	UP^[англ.] NP NP-complete co-NP co-NP-complete AM^[англ.] MA^[англ.] QMA PH ⊕P^[англ.] PP #P #P-complete^[англ.] IP^[англ.] PSPACE PSPACE-complete^[англ.]
Считаются сложными	EXPTIME NEXPTIME^[англ.] EXPSPACE^[англ.] 2-EXPTIME^[англ.] ELEMENTARY^[англ.] R PR^[англ.] RE^[англ.] RE-complete^[англ.] Co-RE^[англ.] Co-RE-complete^[англ.] ALL^[англ.]

NP-полные задачи
Максимизационная задача укладки (упаковки)	Упаковка в контейнеры двумерная упаковка линейная упаковка упаковка по весу упаковка по стоимости Задача о рюкзаке
Теория графов теория множеств	Задача о вершинном покрытии Задача о клике Задача о независимом множестве (наборе) Задача о покрытии множества Задача Штейнера Задача коммивояжёра Обобщённая задача коммивояжёра
Алгоритмические задачи	Задача выполнимости булевых формул (в конъюнктивной нормальной форме)
Логические игры и головоломки	Обобщённые пятнашки (игра в N²-1) задача поиска кратчайшего решения Задачи, решения которых применяются в Тетрис Задача обобщённого судоку Задача о заполнении латинского квадрата Задача какуро
Классы сложности Исследование операций Оптимизация Комбинаторная оптимизация Прикладная математика Теория алгоритмов Динамическое программирование 21 NP-полная задача Карпа

NP-полная задача: различия между версиями

Текущая версия от 23:43, 4 августа 2024

Содержание

Формальное определение

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

Гипотеза P ≠ NP

Примеры NP-полных задач

См. также

Примечания

Литература

Ссылки

Навигация

NP-полная задача: различия между версиями

Текущая версия от 23:43, 4 августа 2024

Формальное определение

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

Гипотеза P ≠ NP

Примеры NP-полных задач

См. также

Примечания

Литература

Ссылки

Навигация

Поиск