Каким будет гипотетически доказательство P=NP?
Будет ли это алгоритм с полиномиальным временем для конкретной NP-полной задачи или существуют просто абстрактные рассуждения, демонстрирующие решения NP-полных задач?
Кажется, что конкретный алгоритм гораздо полезнее. При этом все, что нам нужно сделать для полиномиального решения проблемы NP, - это преобразовать ее в конкретную задачу NP-Complete, для которой доказательство имеет решение, и мы закончили.
15 ответов
P = NP: "Задача 3SAT является классической NP-полной задачей. В этом доказательстве мы демонстрируем алгоритм ее решения, имеющий асимптотическую границу (n^99 log log n). Сначала мы..."
P!= NP: "Предположим, что для задачи 3SAT существовал полиномиальный алгоритм. Это подразумевало бы то, что… что… подразумевает, что мы можем сделать… и затем… и тогда… что невозможно. Все это было основано на алгоритме полиномиального времени для 3SAT. Таким образом, P!= NP."
ОБНОВЛЕНИЕ: Возможно, что-то вроде этой статьи (для P!= NP).
ОБНОВЛЕНИЕ 2: Вот видео Майкла Сипсера, набрасывающего доказательство для P!= NP
Назовите меня пессимистичным, но это будет так:
...
∴, P ≠ NP
QED
Существуют некоторые мета-результаты о том, как не может выглядеть доказательство P=NP или P≠NP. Детали довольно технические, но известно, что доказательство не может быть
релятивизирующий, что означает, что в доказательстве должно использоваться точное определение используемой машины Тьюринга, потому что с некоторыми модификациями ("оракулами", такими как очень мощные инструкции CISC, добавленные в набор команд) P=NP, и с некоторыми другими модификациями, P≠NP. Смотрите также этот блог для хорошего объяснения релятивизации.
естественно, свойство нескольких классических схемных доказательств сложности,
или алгебраизация, обобщение релятивизации.
Это может принять форму демонстрации того, что допущение P ≠ NP приводит к противоречию.
Вероятно, это было бы в форме сокращения от проблемы NP к проблеме P. Смотрите страницу Википедии о сокращениях.
ИЛИ ЖЕ
Как это доказательство, предложенное Vinay Deolalikar.
Возможно, он не связан напрямую с P и NP... Многие теоремы сейчас основаны на P!=NP, поэтому доказательство того, что один предполагаемый факт не соответствует действительности, имело бы большое значение. Даже доказать что-то вроде аппроксимации с постоянным отношением для TS должно быть достаточно IIRC. Я думаю, что существование NPI (GI) и других наборов также основано на P!=NP, поэтому создание любого из них равным P или NP может полностью изменить ситуацию.
ИМХО все происходит сейчас на очень абстрактном уровне. Если кто-то докажет что-нибудь о P=/!=NP, он не должен упоминать ни один из этих наборов или даже конкретную проблему.
Самый простой способ - доказать, что существует решение за полиномиальное время в классе NP-complete. Это проблемы, которые есть в NP и сводятся к одной из известных проблем np. Это означает, что вы могли бы дать более быстрый алгоритм, чтобы доказать исходную проблему, поставленную Стивеном Куком или многими другими, которые также были показаны как NP-Complete. Посмотрите оригинальную статью Ричарда Карпа и эту книгу для более интересных проблем. Было показано, что если вы решите одну из этих проблем, весь класс сложности рухнет. редактировать: я должен добавить, что я разговаривал с моим другом, который изучает квантовые вычисления. Хотя я понятия не имел, что это значит, он сказал, что это определенное доказательство / эксперимент? в квантовом мире может сделать весь класс сложности, я имею в виду все это, спорный. Если кто-то здесь знает больше об этом, пожалуйста, ответьте.
Также были предприняты многочисленные попытки решить проблему без предоставления формального алгоритма. Вы можете попытаться посчитать набор. Есть доказательство Роберта / Сеймора. Люди также пытались решить эту проблему, используя проверенное и проверенное доказательство диагонализации (также использовалось, чтобы показать, что есть проблемы, которые вы никогда не сможете решить). Разборов также показал, что если существуют определенные односторонние функции, то любое доказательство не может дать решение. Это означает, что для решения этого вопроса потребуются новые методы.
Прошло 38 лет с момента публикации оригинальной статьи, и до сих пор нет никаких признаков доказательства. Не только это, но и множество проблем, которые математики ставили до того, как появилось понятие классов сложности, было доказано как NP. Поэтому многие математики и ученые-компьютерщики считают, что некоторые проблемы настолько фундаментальны, что для их решения может потребоваться новый вид математики. Вы должны помнить, что лучшие умы, которые может предложить человеческая раса, решили эту проблему без какого-либо успеха. Я думаю, что должно пройти не менее десятилетий, прежде чем кто-то взломает головоломку. Но даже если существует решение за полиномиальное время, константы или показатель степени могут быть такими большими, что это будет бесполезно в наших задачах.
Существует отличный опрос, который должен ответить на большинство ваших вопросов: http://www.scottaaronson.com/papers/pnp.pdf.
Установите N равным мультипликативному тождеству. Тогда NP = P. QED.;-)
Конечно, описательное доказательство является наиболее полезным, но существуют и другие категории доказательств: возможно, например, предоставить "доказательства существования", которые демонстрируют, что можно найти ответ, не находя (или, иногда, даже предлагая, как найти) этот ответ.
Скорее всего, это будет выглядеть почти так же, как один из этих
Никакого неконструктивного доказательства того, что P=NP на самом деле нет. Это означало бы, что следующий явный алгоритм 3-SAT выполняется за полиномиальное время:
Перечислите все программы. На первом этапе запустите все программы с номером меньше одного шага. Если программа завершается с удовлетворительным вводом в формулу, вернуть true. Если программа завершает работу с формальным доказательством того, что такого ввода не существует, вернуть false.
Если P=NP, то существует программа, которая работает в O(poly(N)) и выводит удовлетворительный ввод в формулу, если такая формула существует.
Если P=coNP, существует программа, которая выполняется в O(poly(N)) и выводит формальное доказательство того, что никакой формулы не существует, если никакой формулы не существует.
Если P=NP, то, поскольку P замкнуто относительно дополнения NP=coNP. Итак, существует программа, которая работает на O(poly(N)) и выполняет обе задачи. Эта программа является k -й программой в перечислении. k есть O (1)! Так как он работает в O(poly(N)), наше моделирование грубой силы требует только
K *O(поли (N))+O(поли (N))^2
раунды, как только он достигает рассматриваемой программы. Таким образом, симуляция грубой силы выполняется за полиномиальное время!
(Обратите внимание, что k имеет экспоненциальный размер программы; этот подход на самом деле неосуществим, но он предполагает, что было бы трудно сделать неконструктивное доказательство того, что P=NP, даже если бы это было так.)
Хороший вопрос; это может принять любую форму. Очевидно, что конкретный алгоритм был бы более полезным, да, но нет никакого определения, что это будет способ, которым будет иметь место теоретическое доказательство P=NP. Принимая во внимание природу NP-полных задач и их распространенность, может показаться, что для решения этих проблем было приложено больше усилий, чем для решения теоретической части уравнения, но это только предположение.
В какой-то степени форма, которую должно иметь такое доказательство, зависит от вашей философской точки зрения (= аксиомы, которые вы считаете верными) - например, как конструктивист вы бы потребовали построения фактического алгоритма, который требует полиномиального времени для решения NP-полная проблема. Это может быть сделано с помощью сокращения, но не с косвенным доказательством. Во всяком случае, это действительно кажется невероятным:)
Доказательство выведет противоречие из предположения о том, что хотя бы один элемент (проблема) NP также не является элементом P.