Проблема P-NP

P - NP проблема (также P≟NP , P против NP ) нерешенная проблема в математике , особенно теория сложности в теоретической информатике . Вопрос в том , идентичны ли набор всех проблем, которые можно быстро решить ( ), и набор всех проблем, для которых предлагаемое решение может быть быстро проверено на правильность ( ). ${\ displaystyle P}$${\ displaystyle NP}$

Понятно, что вы можете быстро проверить правильность решения для всех задач, которые можно решить быстро , но обратное неясно: для некоторых задач есть алгоритм, который может быстро проверить предлагаемое решение , но он не может ни алгоритм можно было бы найти, что быстро найти правильное решение, и невозможно было бы доказать невозможность такого алгоритма. Таким образом, вопрос не решен. Если бы нужно было найти алгоритм для всех быстро тестируемых задач, который также быстро их решал бы, то это применимо . Если бы можно было показать хотя бы для одной проблемы, что ее в принципе невозможно решить быстро , это было бы доказано. ${\ displaystyle NP}$${\ displaystyle P = NP}$${\ displaystyle NP}$${\ Displaystyle P \ neq NP}$

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

история

Проблема P-NP была признана в начале 1970-х благодаря независимой работе Стивена Кука и Леонида Левина . Она считается одной из важнейших нерешенных проблем информатики и была включена в список проблем тысячелетия Институтом математики Клэя .

Как позже стало известно, проблема уже может быть сформулирована в письме Курта Гёделя , которое последний отправил Джону фон Нейману незадолго до своей смерти (20 марта 1956 г.). Еще одна ранняя формулировка содержится в письме Джона Форбса Нэша в Агентство национальной безопасности от 1955 года о криптографии.

P и NP

Класс сложности NP в предположении P ≠ NP. В этом случае NP также содержит проблемы над P, которые не являются NP-полными .

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

Мера, используемая здесь для вычисления усилий, - это количество шагов вычисления, которое требуется алгоритму для решения проблемы ( временная сложность ). Чтобы четко указать объем вычислений, также требуются формальные модели машин для представления алгоритмов решения. Часто используемой моделью является детерминированная машина Тьюринга , которую можно рассматривать как абстракцию реального компьютера.

П.

Одна из категорий проблем - класс сложности . Он содержит задачи, для которых существует детерминированная машина Тьюринга, решающая задачу за полиномиальное время . Это означает, что существует многочлен с , так что машине Тьюринга не требуется больше, чем шаги вычисления для любого экземпляра проблемы (с длиной входных данных) . Таким образом, задачи из могут быть решены детерминированно за полиномиальное время . ${\ displaystyle P}$${\ Displaystyle е (п) = п ^ {к} + с}$${\ displaystyle c, k \ in \ mathbb {N}}$${\ displaystyle n}$${\ displaystyle f (n)}$${\ displaystyle P}$

Упомянутая выше проблема сортировки относится к P, потому что существуют алгоритмы, которые сортируют количество записей (учетных карточек) за время, ограниченное квадратичной функцией в . Другой пример проблемы на фиг.4 - это проблема оценки схемы . ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle P}$

Разница между машиной Тьюринга и реальными компьютерами здесь не имеет значения, потому что каждый алгоритм, который решает задачу за полиномиальное время на реальном компьютере, также может быть реализован на машине Тьюринга за полиномиальное время (хотя степень полинома, ограничивающая время выполнения, равна в Обычно будет выше).

НП

Другая модель машины - это недетерминированная машина Тьюринга (NTM), она является обобщением детерминированного варианта. В определенной ситуации у НТМ может быть несколько вариантов продолжения расчета, поэтому метод расчета не всегда четко определен. Это теоретическая модель, нет реальных компьютеров, которые могли бы таким образом разветвлять свой путь вычислений. Его полезность в этом контексте заключается в том, что его можно использовать для определения другого класса сложности, который содержит много проблем, представляющих практический интерес, из которых еще неизвестно, в них ли . ${\ displaystyle NP}$${\ displaystyle P}$

${\ displaystyle NP}$определяется как набор задач, решаемых НТМ за полиномиальное время. Детерминированная машина Тьюринга - это частный случай NTM, она не требует разветвления вычислительного пути. Поэтому это подмножество из . ${\ displaystyle P}$${\ displaystyle NP}$

Можно определить эквивалентным образом как набор проблем, из которых можно решить за полиномиальное время с помощью детерминированной машины Тьюринга, применимо ли предложенное решение. Например, в настоящее время неизвестен детерминированный алгоритм, учитывающий данное число за полиномиальное время . Однако очень легко проверить, делит ли предложенный множитель число без остатка и, следовательно, является ли множитель числа. ${\ displaystyle NP}$

P = NP?

Связь задач в P и NP и NP-сложных и NP-полных

Неизвестно , идентичны ли эти два класса и , т.е. могут ли даже самые сложные задачи этого класса быть эффективно решены с помощью детерминированных машин. Для того , чтобы формально понять концепцию «самой сложной проблемой в », понятия NP полноты и были суровости NP введены. Проблема X является NP-трудным , если можно уменьшить каждую проблему в X по полиномиальному сокращению времени . Если кто-то найдет NP-сложную задачу X, которую можно решить детерминированно за полиномиальное время, можно также решить каждую задачу за детерминированно полиномиальное время, уменьшив ее до X, и это будет показано. Проблема, лежащая в основе и являющаяся NP-сложной, называется NP-полной. ${\ displaystyle P}$${\ displaystyle NP}$${\ displaystyle NP}$${\ displaystyle NP}$${\ displaystyle NP}$${\ displaystyle NP}$${\ displaystyle P = NP}$${\ displaystyle NP}$

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

Также было показано: если есть и, следовательно, NP-полные задачи не входят , то существуют также задачи, в которых не являются ни NP-полными, ни in , которые представляют собой промежуточный уровень сложности. Кандидатом на решение такой проблемы является проблема изоморфизма графов , для которой до сих пор мы не знаем, является ли она NP-полной или нет. ${\ Displaystyle P \ neq NP}$${\ displaystyle P}$${\ displaystyle NP}$${\ displaystyle P}$${\ displaystyle P}$

Решение проблемы

Пока известны только алгоритмы экспоненциального времени на детерминированных вычислительных машинах для точного решения NP-полных задач. Однако не было доказано, что для решения не существует алгоритмов с полиномиальным временем, в отличие от другого класса задач, которые гарантированно требуют как минимум экспоненциального времени выполнения ( EXPTIME -полные задачи) и, таким образом, явно выходят за рамки этого класса. . Если бы нужно было найти полиномиальный ограниченный по времени алгоритм на детерминированных вычислительных машинах для одной из этих NP-полных задач для всех входов (классов ), то любую проблему можно было бы свести к ней путем полиномиального сокращения времени и, таким образом, решить за детерминированное полиномиальное время; в этом случае было бы . ${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle NP}$${\ displaystyle P = NP}$

Поскольку разработать такой алгоритм пока не удалось, большинство экспертов полагают, что это правда. Это можно доказать математически, доказав для задачи из класса, что не существует детерминированного алгоритма полиномиального времени для ее решения. ${\ Displaystyle P \ neq NP}$${\ displaystyle NP}$

Возможные сценарии решения проблемы:

• Это доказано .${\ Displaystyle P \ neq NP}$
• Доказано, что он логически не зависит от ZFC .${\ Displaystyle P \ neq NP}$
• Это доказывает, предлагая эффективный алгоритм для NP-полной задачи .${\ displaystyle P = NP}$
• Чтобы доказать, что это правда, используются неконструктивные методы , то есть без построения явного алгоритма.${\ displaystyle P = NP}$

Сложность проблемы подтверждается тем фактом, что для различных методов доказательства уже было показано, что их одних недостаточно, чтобы прояснить вопрос.

Относительные методы доказательства

Доказательство связи между двумя классами сложности является относительным, если связь сохраняется для любых добавленных оракулов . Класс методов релятивизирующего доказательства включает, например, Б. также метод диагонализации, который часто используется в теории сложности . Если кто-то показывает, например, посредством диагонализации, то автоматически применяется к каждому оракулу . Следующая важная теорема Теодора Бейкера, Джона Гилла и Роберта Соловея доказывает, что релятивизирующие методы доказательства не могут быть эффективным средством для решения проблемы P-NP и что многие методы атаки на проблему P-NP из теоретической информатики в результате терпят неудачу: ${\ displaystyle K \ neq K '}$${\ displaystyle K ^ {A} \ neq K '^ {A}}$${\ displaystyle A}$

Есть два оракула и , так что и .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ operatorname {P} ^ {A} = \ operatorname {NP} ^ {A}}$${\ Displaystyle \ OperatorName {P} ^ {B} \ neq \ OperatorName {NP} ^ {B}}$

Естественное свидетельство

Александр Разборов и Стивен Рудич ввели понятие «естественные доказательства» (англ. Natural proofs ) в своей работе 1994 года. Исходя из общего предположения, что существуют определенные односторонние функции , они продемонстрировали невозможность разделения с помощью какой-то комбинаторной техники доказательства. ${\ displaystyle P}$${\ displaystyle NP}$

Проще говоря, доказательство является «естественным», если оно определяет критерий «простоты» и показывает, что функции обладают этим свойством и что существует NP-полная проблема, не обладающая этим свойством. Критерий «простоты» должен, с одной стороны, применяться к достаточно большому количеству функций, а с другой стороны, быть достаточно легким для проверки. ${\ displaystyle P}$

Попытки доказать

Хотя проблема P-NP обычно считается нерешенной, многие любители и профессиональные исследователи опубликовали различные решения. Герхард Вёгингер проводит сбор доказательств, в котором в сентябре 2016 года перечислены 62 предполагаемых доказательства , 50 доказательств , два доказательства неразрешимости проблемы и одно доказательство неразрешимости. Среди всей этой работы есть только одна, которая появилась в рецензируемом журнале, которая была тщательно проверена экспертами в этой области и чья правильность признана общим исследовательским сообществом: работа Михалиса Яннакакиса (эта статья не прояснить вопрос P по сравнению с NP, но просто показывает, что какой-либо конкретный подход к прояснению этого вопроса никогда не сработает). ${\ displaystyle P = NP}$${\ Displaystyle P \ neq NP}$

Совсем недавно стала известна попытка доказать это 6 августа 2010 года математиком Виней Деолаликаром, нанятым Hewlett-Packard . Его быстро сочли опровергнутым, но он заслуживает похвалы за то, что время от времени привлекал внимание к этой теме как в общественных, так и в специализированных кругах.${\ Displaystyle P \ neq NP}$

Практическая значимость

Многие практически актуальные задачи являются NP-полными. Поэтому решение проблемы P-NP может иметь большое значение. Доказательство означало бы, что существуют алгоритмы для задач класса, которые решают их за полиномиальное время. Однако, поскольку за последние десятилетия не было найдено ни одного алгоритма, несмотря на интенсивный поиск, который решает NP-полную задачу за полиномиальное время, эксперты сомневаются в том, что такие алгоритмы вообще существуют; ч., можно предположить . ${\ displaystyle P = NP}$${\ displaystyle NP}$${\ Displaystyle P \ neq NP}$

Многие NP-полные задачи, такие как набегающий коммивояжера проблемы , в рюкзаке проблемы или проблемы раскраске графов , может теоретически быть оптимально решена в короткие сроки в этом случае . Однако показатели и константы функции времени выполнения полиномиального метода также могут быть настолько высокими, что один из ранее известных методов решения, например Б. приблизительный или вероятностный , всегда лучше. ${\ displaystyle P = NP}$

С доказательством того , что проблемы NP, наконец, будут классифицированы как трудно решаемые. в настоящее время является предположением большинства ученых, и его доказательство будет менее важным, чем доказательство того, что . ${\ Displaystyle P \ neq NP}$${\ Displaystyle P \ neq NP}$${\ displaystyle P = NP}$

В криптологии , в отличие от большинства других областей, желательным свойством является сложность. Безопасность некоторых методов асимметричного шифрования основана только на этом факторе. Алгоритм NP может взломать любую асимметричную криптосистему, «угадав» секретный ключ и используя метод, который будет использовать фактический получатель сообщения, эффективно расшифруя его и, таким образом, проверив ключ. Таким образом, доказательство того , что есть, означало бы, что есть перспектива взлома этих криптосистем на практике. Соответственно, решение проблемы P-NP связано с открытым вопросом о существовании односторонних функций . Если есть, то последует. ${\ displaystyle P = NP}$${\ Displaystyle P \ neq NP}$

Смотри тоже

• Карпс 21 NP-полные задачи
• Параметризованный алгоритм

литература

• Скотт Ааронсон : в: (ред.) Джон Форбс Нэш, Майкл Рассиас, Математика открытых задач, Springer, 2016, стр. 1-122.${\ Displaystyle P \; {\ stackrel {?} {=}} \; NP}$
• Стивен А. Кук : против проблемы , Институт математики Клэя (Проблемы тысячелетия)${\ displaystyle P}$${\ displaystyle NP}$
• Лэнс Фортноу : Статус проблемы${\ displaystyle P = NP}$ , общ. ACM, Том 52, 2009 г., стр. 78-86, онлайн
• Лэнс Фортноу : Золотой билет. и поиск невозможного${\ displaystyle P, NP}$ , Princeton University Press, 2013
• Ричард Дж Lipton: Вопрос и Гёделя Затерянный письмо , Springer 2010${\ displaystyle P = NP}$

Индивидуальные доказательства

1. ↑ John Dawson Kurt Gödel - Leben und Werk , Springer Verlag 1997, p. 177, там цитируется письмо
2. ↑ Янис Хартманис Гёдель, фон Нейман и проблема P? = NP , Bulletin European Assoc. Теор. Компьютерные науки, 38, 1989, стр. 101-107.
3. ↑ Письмо Гёделя, блог Липтона , с английским переводом
4. ↑ Майкл Сипсер История и статус вопроса «П против НП» , 24-й протокол STOC, 1992, стр. 603-618
5. ↑ Скотт Ааронсон, P =? Н.П., в: Нэш, Рассиас, Открытые задачи по математике, Springer, 2016, стр. 1 (с цитатой из письма)
6. ↑ Национальный криптологический музей открывает новую экспозицию, посвященную доктору Др. Джон Нэш , NSA 2012. Отрывок на стр. 4 письма 1955 года гласит: Теперь моя общая гипотеза такова: почти для всех достаточно сложных типов шифрования, особенно там, где инструкции, данные разными частями ключа, комплексно взаимодействуют с каждым из них. другие - при определении их окончательного воздействия на шифрование, средняя длина вычисления ключа увеличивается экспоненциально с увеличением длины ключа или, другими словами, информационного содержания ключа. Значение этой общей гипотезы, если предположить ее истинность, легко увидеть. Это означает, что вполне реально разработать шифры, которые невозможно взломать. .... Природа этой гипотезы такова, что я не могу ее доказать даже для особого типа шифров. Я тоже не жду, что это будет доказано.
7. ^ Ричард Э. Ладнер: О структуре полиномиальной сводимости времени. В: Журнал АКМ. 22, № 1, 1975, стр. 151-171 (DOI : 10.1145 / 321864.321877 ).
8. ↑ Дональд Кнут считает этот вариант правильным, см. Аргументацию и интерпретацию в « Двадцать вопросов для Дональда Кнута», май 2014 г. , вопрос 17.
9. ^ Теодор Бейкер, Джон Гилл, Роберт Соловей: релятивизации вопроса P =? NP. В: SIAM Journal on Computing. 4, No. 4, 1975, pp. 431-442, 1975 ( DOI: 10.1137 / 0204037 ).
10. ↑ Герхард Вёгингер: страница P против NP. 26 сентября 2016, доступ к 3 апреля 2020 . 
11. ↑ Newsticker Heise 2010
12. ↑ Александр Назарян: Глубочайшая математическая задача . В: The New Yorker . 2 мая, 2013. Проверено 15 февраля, 2017.
13. ↑ Его блог об этом со статьей в исправленной версии.

веб ссылки

• "Страница P-против-NP" : коллекция ссылок на научные статьи и попытки решения проблемы P-NP Герхарда Вёгингера.