Каким будет гипотетическое доказательство P = NP?

Question

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

Кажется, что конкретный алгоритм гораздо полезнее. При этом все, что нам нужно сделать для полиномиального решения проблемы NP, - это преобразовать ее в конкретную задачу NP-Complete, для которой доказательство имеет решение, и мы закончили.

Answer 1

Никаких неконструктивных доказательств того, что P = NP на самом деле нет. Это означает, что следующий явный алгоритм 3-SAT выполняется за полиномиальное время:

Перечислите все программы. На раунде 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, даже если бы это было так.)

Answer 2

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

Answer 3

Интересное прочтение, которое в некоторой степени связано с этим

Answer 4

Доказательство выведет противоречие из предположения, что хотя бы один элемент (проблема) NP также не является элементом P.

Answer 5

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