Каким гипотетически было бы доказательство P = NP?
https://stackoverflow.com/questions/900273
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Будет ли это алгоритм полиномиального времени для конкретной NP-полной задачи или просто абстрактные рассуждения, демонстрирующие существование решений NP-полных задач?
Кажется, что конкретный алгоритм a гораздо более полезен.С его помощью все, что нам нужно будет сделать для полиномиального решения NP-задачи, - это преобразовать ее в конкретную NP-полную задачу, для которой доказательство имеет решение, и мы закончили.
Решение
P = NP:"Тот 3САТ задача - это классическая NP-полная задача.В этом доказательстве мы демонстрируем алгоритм для его решения, который имеет асимптотическую оценку (n ^ 99 log log n).Сначала мы ..."
P != NP:"Предположим , что существовал полиномиальный алгоритм для 3САТ проблема.Это означало бы , что ....который мимо .....подразумевает , что мы можем сделать ....а потом ...а потом ...что невозможно.Все это было основано на алгоритме полиномиального времени для 3SAT.Таким образом, P != NP."
Обновить:Возможно, что-то вроде этот документ (для P != NP).
ОБНОВЛЕНИЕ 2: Вот видео Майкла Сипсера , набрасывающего доказательство для P != NP
Другие советы
Можете назвать меня пессимистом, но так оно и будет:
...
∴, P ≠ NP
КЭД
Есть некоторые мета-результаты о том, что доказательство P = NP или P≠ NP может не похож.Детали довольно технические, но известно, что доказательство не может быть
релятивизирующий, что в некотором роде означает, что в доказательстве должно использоваться точное определение используемой машины Тьюринга, потому что с некоторыми модификациями ("оракулы", такие как очень мощные инструкции CISC, добавленные в набор команд) P = NP, а с некоторыми другими модификациями P≠NP.Смотрите также это сообщение в блоге за хорошее объяснение релятивизации.
Натуральные, свойство нескольких классических сложность схемы доказательства,
или алгебризующий, обобщение релятивизации.
Это могло бы принять форму демонстрации того, что допущение P ≠ NP приводит к противоречию.
Возможно, это не связано с P и NP прямым способом...Многие теоремы сейчас основаны на P! = NP, поэтому доказательство того, что один предполагаемый факт не соответствует действительности, имело бы большое значение.Даже доказательства чего-то вроде аппроксимации постоянным коэффициентом для TS должно быть достаточно IIRC.Я думаю, существование NPI (GI) и других множеств также основано на P!= NP, поэтому приравнивание любого из них к P или NP может полностью изменить ситуацию.
ИМХО, сейчас все происходит на очень абстрактном уровне.Если кто-то докажет что-нибудь о P = /!= NP, ему не обязательно упоминать ни один из этих наборов или даже конкретную проблему.
Вероятно, это было бы в форме редукции от NP-задачи к P-задаче.Смотрите страницу Википедии на сокращения.
или
Вот так доказательство предложено Винаем Деолаликаром.
Установите N равным мультипликативному тождеству.Тогда NP = P.КЭД.;-)
Самый простой способ - доказать, что существует решение задач класса NP-complete за полиномиальное время.Это задачи, которые находятся в NP и сводимы к одной из известных np-задач.Это означает, что вы могли бы дать более быстрый алгоритм для доказательства оригинальная проблема , поставленная Стивеном Куком или многие другие, которые также были показаны как NP-Полные.Посмотрите фильм Ричарда Карпа основополагающий документ и эта книга для более интересных задач.Было показано, что если вы решаете одну из этих задач, весь класс сложности разрушается.Редактировать:Я должен добавить, что я разговаривал со своим другом, который изучает квантовые вычисления.Хотя я понятия не имел, что это значит, он сказал, что определенное доказательство / эксперимент?в квантовом мире это могло бы сделать весь класс сложности, я имею в виду все это, спорным.Если кто-нибудь здесь знает больше об этом, пожалуйста, ответьте.
Также были многочисленные попытки решить проблему без предоставления формального алгоритма.Вы могли бы попытаться сосчитать набор.Вот доказательство Роберта / Сеймора.Люди также пытались решить ее, используя проверенное доказательство диагонализации (также используемое, чтобы показать, что есть проблемы, которые вы никогда не сможете решить).Разборов также показал, что если существуют определенные односторонние функции, то любое доказательство не может дать решения.Это означает, что для решения этого вопроса потребуются новые методы.
Прошло 38 лет с тех пор, как была опубликована оригинальная статья, и до сих пор нет никаких признаков доказательства.Было показано, что не только это, но и многие проблемы, которые математики ставили перед собой до появления понятия классов сложности, являются NP.Поэтому многие математики и специалисты в области информатики считают, что некоторые из проблем настолько фундаментальны, что для их решения может потребоваться новый вид математики.Вы должны иметь в виду, что лучшие умы, которые может предложить человеческая раса, взялись за эту проблему без какого-либо успеха.Я думаю, должно пройти по меньшей мере несколько десятилетий, прежде чем кто-нибудь разгадает головоломку.Но даже если существует решение за полиномиальное время, константы или показатель степени могут быть настолько большими, что это было бы бесполезно в наших задачах.
Доступен отличный опрос, который должен ответить на большинство ваших вопросов: http://www.scottaaronson.com/papers/pnp.pdf.
Конечно, описательное доказательство является наиболее полезным, но существуют и другие категории доказательств:можно, например, предоставить "доказательства существования", которые демонстрируют, что это возможно найти ответ, не найдя (или, иногда, даже не предложив, как найти) этот ответ.
Вероятно, это выглядело бы почти точно так же, как один из эти
Хороший вопрос;это могло принять любую форму.Очевидно, что конкретный алгоритм был бы более полезным, да, но нет уверенности в том, что именно так будет происходить теоретическое доказательство P = NP.Учитывая природу NP-полных задач и то, насколько они распространены, может показаться, что на решение этих задач было затрачено больше усилий, чем на решение теоретической части уравнения, но это всего лишь предположение.
Любое неконструктивное доказательство того, что P = NP на самом деле таковым не является.Это означало бы, что следующий явный алгоритм 3-SAT выполняется за полиномиальное время:
Перечислите все программы.На круглом i, запустить все программы, пронумерованные менее i на один шаг.Если программа завершается с удовлетворяющие входные данные в формулу, вернуть верно.Если программа завершается с формальное доказательство того, что такого ввода не существует, вернуть ложь.
Если 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, даже если бы это было так.)
В некоторой степени форма, которую должно иметь такое доказательство, зависит от вашей философской точки зрения (= аксиом, которые вы считаете истинными) - например, как конструктивист вы бы потребовали построения реального алгоритма, который требует полиномиального времени для решения NP-полной задачи.Это можно было бы сделать с помощью сокращения, но не с помощью косвенного доказательства.Во всяком случае, это действительно кажется очень маловероятным :)
Доказательство привело бы к противоречию из предположения, что по крайней мере один элемент (проблема) NP также не является элементом P.
