Будет ли это алгоритм полиномиального времени для конкретной NP-полной проблемы или существуют только абстрактные рассуждения, демонстрирующие решения NP-полных проблем?
Кажется, что конкретный альгоизм гораздо полезнее. При этом все, что нам нужно сделать, чтобы полиномиально решить проблему NP, - это преобразовать ее в конкретную NP-полную проблему, для которой доказательство имеет решение, и мы закончили.
P = NP: "Проблема 3SAT является классической NP полной проблемой. В этом доказательстве мы демонстрируем алгоритм ее решения, который асимптотическая оценка (n ^ 99 log log n). Сначала мы..."
P!= NP: "Предположим, что для проблемы 3SAT существует полиномиальный алгоритм. Это означало бы, что.... который by..... подразумевает, что мы можем делать.... и затем... и затем... что невозможно. Все это было основано на алгоритме полиномиального времени для 3SAT. Таким образом, P!= NP."
UPDATE. Возможно, что-то вроде этой статьи (для P!= NP).
ОБНОВЛЕНИЕ 2: Здесь видео Майкла Сипсера, набросающего доказательство для P!= NP
Назовите меня пессимистичным, но это будет так:
...
∴, P ≠ NP
КЭД
Есть некоторые мета-результаты о том, что не может выглядеть доказательство P = NP или P ≠ NP. Детали весьма технические, но известно, что доказательство не может быть
релятивизация, что означает, что доказательство должно использовать точное определение используемой машины Тьюринга, поскольку с некоторыми модификации ( "оракулы", такие как очень мощные инструкции CISC, добавленные к набору команд) P = NP, а также с некоторыми другими модификациями P ≠ NP. См. Также этот пост в блоге для приятного объяснения релятивизации.
natural, свойство нескольких классических сложность схемы,
или алгебраизация, обобщение релятивизации.
Это может принять форму демонстрации того, что, предполагая P & ne; NP приводит к противоречию.
Он может быть не связан с P и NP простым способом... Многие теоремы теперь основаны на P!= NP, поэтому доказать, что один предполагаемый факт неверен, имел бы большое значение. Даже доказать что-то вроде приближения постоянного отношения для TS должно быть достаточно IIRC. Я думаю, что существование NPI (GI) и других множеств также основано на P!= NP, поэтому любое из них, равное P или NP, может полностью изменить ситуацию.
ИМХО все происходит сейчас на очень абстрактном уровне. Если кто-то докажет что-либо о P =/!= NP, он не должен упоминать ни один из этих наборов или даже конкретную проблему.
ИЛИ
Как этот proof, предложенный Винаем Деолиликаром.
Множество N равно мультипликативному тождеству. Тогда NP = P. QED.; -)
Самый простой способ - доказать, что существует полиномиальное решение времени для задач класса NP-полных. Это проблемы, которые возникают в NP и сводятся к одной из известных проблем np. Это означает, что вы могли бы дать более быстрый алгоритм, чтобы доказать оригинальную проблему, поставленную Stephen Cook или многими другими, которые также показали, что NP-Complete, См. Ричард Карп оригинальная бумага и эта книга для более интересные проблемы. Было показано, что если вы решите одну из этих проблем, весь класс сложности рухнет. edit: Я должен добавить, что я разговаривал с моим другом, который изучает квантовые вычисления. Хотя я понятия не имел, что это значит, он сказал, что это доказательство/эксперимент? в квантовом мире может сделать весь класс сложности, я имею в виду все это, спорный. Если кто-нибудь знает об этом больше, ответьте.
Были также многочисленные попытки решить проблему без предоставления формального алгоритма. Вы можете попробовать подсчитать набор. Theres доказательство Роберт /Seymore. Люди также пытались решить это, используя проверенное доказательство диагонализации (также используется, чтобы показать, что есть проблемы, которые вы никогда не сможете решить). Разборов также показал, что если есть определенные односторонние функции, то любое доказательство не может дать разрешения. Это означает, что для решения этого вопроса потребуются новые методы.
Прошло 38 лет с момента опубликования оригинальной статьи, и до сих пор нет доказательств. Было показано, что не только это, но и множество проблем, которые ставили математики перед тем, как появилось понятие классов сложности, было показано как NP. Поэтому многие математики и компьютерщики считают, что некоторые из проблем настолько фундаментальны, что для решения проблемы может понадобиться новый вид математики. Вы должны иметь в виду, что лучшая человеческая раса, которую может предложить, решила эту проблему без каких-либо успехов. Я думаю, что это должно быть по крайней мере за несколько десятилетий, прежде чем кто-то сломает головоломку. Но даже если существует полиномиальное временное решение, константы или экспоненты могут быть настолько большими, что в наших задачах это будет бесполезно.
Существует отличный обзор, который должен отвечать на большинство ваших вопросов: http://www.scottaaronson.com/papers/pnp.pdf.
Конечно, наиболее полезным является описательное доказательство, но существуют и другие категории доказательств: возможно, например, предоставить "доказательства существования", которые демонстрируют, что возможно найти ответ не найдя (или, иногда, даже предлагая, как найти) ответ.
Вероятно, он выглядит почти как один из этих
Хороший вопрос; он может принимать любую форму. Очевидно, что конкретный алгоритм был бы более полезен, да, но нет никакого определения, что это будет так, что будет иметься теоретическое доказательство P = NP. Учитывая, что характер NP-полных проблем и насколько они распространены, казалось бы, в решение этих проблем было приложено больше усилий, чем было принято в решении теоретической аргументационной стороны уравнения, но это просто предположение.
Любое неконструктивное доказательство того, что P = NP действительно нет. Это означало бы, что следующий явный алгоритм 3-SAT выполняется в полиномиальное время:
Перечислить все программы. На круглом i запустите все пронумерованные программы менее i за один шаг. Если программа завершается удовлетворяющий входному сигналу в формулу, верните true. Если программа заканчивается формальным доказательством того, что такой вход не существует, возврат ложь.
Если 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)), для моделирования грубой силы требуется только
к * О (поли (N)) + O (поли (N)) ^ 2
раунды, как только он достигнет рассматриваемой программы. Таким образом, симуляция грубой силы выполняется в полиномиальное время!
(Заметим, что k является экспоненциальным по размеру программы, этот подход на самом деле невозможен, но он предполагает, что было бы трудно сделать неконструктивное доказательство того, что P = NP, даже если бы это было так.)
В какой-то степени форма такого доказательства должна быть зависит от вашей философской точки зрения (= аксиомы, которые вы считаете истинными) - например, как contructivist, вы потребовали бы построения реального алгоритма, который требует полиномиального времени для решения NP-полной проблемы. Это можно сделать, используя сокращение, но не с косвенным доказательством. Во всяком случае, это кажется очень маловероятным:)
Доказательство выводит противоречие из предположения, что хотя бы один элемент (задача) NP не является также элементом P.