Полнота НП

Установить диаграмму возможных взаимосвязей между P , NP и множествами NP-сложных и NP-полных задач.

В информатике , проблема называется NP-полной ( полная для класса задач , которые могут быть решены недетерминированно в полиномиальное время) , если это одна из самых сложных задач в классе NP , то есть одновременно в НП и NP-трудной является. В просторечии это означает, что ее, вероятно, нельзя решить эффективно.

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

Проблема решения является NP-полной, если она

• относится к классу сложности NP : детерминированно работающему компьютеру требуется лишь много полиномиального времени, чтобы решить, действительно ли предложенное решение связанной задачи поиска является решением, и
• Одна из NP-сложных проблем: все другие проблемы, решения которых можно проверить детерминированно за полиномиальное время, можно проследить до самой проблемы таким образом, что это отслеживание на детерминированном компьютере занимает самое большее полиномиальное время. Говорят о полиномиальном сокращении времени .

Класс всех NP-полных задач обозначается NP-C (полный). Свойства этих и других классов исследуются в теории сложности , отрасли теоретической информатики .

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

Многие важные проблемы, возникающие на практике, являются NP-полными, что делает NP-полноту центральным понятием в информатике. Это значение еще больше усиливается так называемой проблемой P-NP :

1. Для любой NP-полной задачи можно было показать, что ее можно решить за полиномиальное время.
2. Если бы только одна из этих проблем была решена за полиномиальное время, то каждая проблема в NP была бы разрешима за полиномиальное время, что могло бы (но не обязательно иметь) большое практическое значение.

С тех пор, как Кук представил NP-полноту, полнота стала общей концепцией для любого класса сложности.

история

Концепция NP-полноты была введена в 1971 году Стивеном А. Куком в том, что сейчас известно как теорема Кука . В нем он показал, что проблема выполнимости логики высказываний является NP-полной. Сегодня намного проще конструктивно доказательство существования таких проблем, но языки , используемые для них очень искусственно. Заслуга Кука также состоит в том, что он предоставил это свидетельство особенно интересного языка.

Основываясь на работе Кука, Ричард Карп в 1972 году представил еще одну революционную работу, которая сделала теорию NP-полноты еще более популярной. Заслуга Карпа состоит в том, что он последовательно использовал технику полиномиального сокращения времени , чтобы доказать NP-полноту еще для 21 популярной задачи .

определение

Проблема (точнее: проблема решения ) L называется NP-полной тогда и только тогда, когда:

• L принадлежит классу NP , т. Е. И${\ displaystyle L \ in {\ rm {NP}}}$
• L является NP-трудной , то есть .${\ displaystyle \ forall L '\ in {\ rm {NP}}: L' \ prevq _ {p} L}$

Последнее условие означает , что каждая проблема в NP может быть сведена к L с помощью полиномиального сокращения времени .

Доказательство полноты НП

Доказательство первого свойства для данной задачи обычно несложно. Один «угадывает» решение и показывает, что можно проверить за полиномиальное время , действительно ли решение применимо. При угадывании (правильного) решения снова можно найти недетерминизм .

Доказательство второго свойства, которое само по себе называется NP-hard (или путем неправильного обратного перевода с английского NP-hard на NP-hard ), является более трудным, особенно когда речь идет о формулировке любых проблем. в НП показать. Следовательно, обычно берется аналогичная проблема, для которой уже известна NP-полнота, и сводится к задаче, для которой должно быть показано свойство NP-серьезности. Из транзитивности из полиномиального сокращения времени это следует , что все другие проблемы из NP могут также быть сведены к рассматриваемой проблеме.

Строго говоря, приведенное выше определение требует доказательства существования. Не сразу очевидно, что такие проблемы вообще существуют. Однако такую ​​задачу легко построить. Однако задача, построенная таким образом, вряд ли актуальна на практике. Однако Кук смог показать, что проблема выполнимости логики высказываний является NP-полной , и, таким образом, предоставил доказательства проблемы, актуальной на практике. В отличие от других задач, это доказательство, конечно, еще не могло быть выполнено через транзитивность полиномиальных сокращений времени, как показано выше, и должно было быть выполнено напрямую.

Эквивалентность NP

NP-полнота определяется только для задач решения, то есть для проблем, которые можно проследить до словесной проблемы формального языка, для которых ответ либо да, либо нет . Для задач оптимизации и поисковых задач есть обозначение NP эквивалентности .

Приближение

Проблемы, которые лежат в NP, могут быть далее подразделены с точки зрения их сложности, в зависимости от того, насколько хорошо они могут быть решены приблизительно . График окраски проблема, например, может быть аппроксимирована только очень слабо, в то время как другие проблемы могут быть аппроксимированы , а также по желанию с применением так называемых приближенных схем.

Сильная NP-полнота

NP-полная задача называется строго NP-полной, если она также является NP-полной, когда она ограничена такими входными экземплярами, которые содержат только числа (как числовые параметры), размер которых полиномиально ограничен по отношению к входной длине (такая проблема всегда в НП). Другими словами: если вы измените задачу таким образом, что все числовые параметры в унарной системе находятся на входе, она останется NP-полной. Для задач, которые являются сильно NP-полными, не существует псевдополиномиальных алгоритмов в предположении, что NP не равно P. Это алгоритмы, время выполнения которых является полиномиальным, если размер всех чисел, встречающихся во входных данных, полиномиально ограничен входной длиной.

Примером задачи, для которой существует псевдополиномиальный алгоритм, является задача о рюкзаке . С помощью алгоритмов, основанных на принципе динамического программирования , можно достичь ограниченного времени выполнения. Таким образом, время вычислений является полиномиальным, если число (предел для максимально допустимого значения полезности) является полиномиальным только по отношению к входной длине . Такие NP-полные задачи с псевдополиномиальным алгоритмом также называются слабо NP-полными .${\ Displaystyle {\ mathcal {O}} (п ^ {2} \ cdot V)}$${\ displaystyle V}$${\ displaystyle n}$

зыбь

1. ↑ См. Стр. 157 книги Юрая Хромковича «Алгоритмика для сложных задач: введение в комбинаторную оптимизацию, рандомизацию, аппроксимацию и эвристику», опубликованной Springer Verlag, 2001, ISBN 3519004445 , ISBN 9783540668602 .
2. ^ Лесли Холл: вычислительная сложность. Проверено 10 декабря 2012 года . 

литература

• Майкл Р. Гэри и Дэвид С. Джонсон: Компьютеры и несговорчивость: Руководство по теории NP-полноты . Фриман, Сан-Франциско, 1978, ISBN 0716710455
• Стивен А. Кук: Сложность процедур доказательства теорем . В Ежегодном симпозиуме ACM по теории вычислений (STOC) , стр 151-158, 1971.

веб ссылки

• NPC (NP-Complete) . В кн . : Зоопарк сложности. (Английский)
• Сборник задач оптимизации NP (английский)
• Результаты сложности для задачи планирования (английский)