На что доказательство P=NP было бы похоже, гипотетически?

При использовании времени Joda используйте функцию Math.ceil ():

double quarter = Math.ceil(new Double(jodaDate.getMonthOfYear()) / 3.0);
17
задан tanascius 16 February 2010 в 17:59
поделиться

15 ответов

P = NP: "The 3SAT problem is a classic NP complete problem. In this proof, we demonstrate an algorithm to solve it that has an asymptotic bound of (n^99 log log n). First we ..."

P != NP: "Assume there was a polynomial algorithm for the 3SAT problem. This would imply that .... which by ..... implies we can do .... and then ... and then ... which is impossible. This was all predicated on a polynomial time algorithm for 3SAT. Thus P != NP."

UPDATE: Perhaps something like this paper (for P != NP).

UPDATE 2: Here's a video of Michael Sipser sketching out a proof for P != NP

36
ответ дан 30 November 2019 в 09:58
поделиться

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

0
ответ дан 30 November 2019 в 09:58
поделиться

Есть несколько мета-результатов о том, как может выглядеть доказательство P = NP или P proof NP не . Детали довольно технические, но известно, что доказательство не может быть

  • релятивизирующим , что означает, что в доказательстве должно использоваться точное определение используемой машины Тьюринга, поскольку с некоторыми модификациями («оракулы») (например, очень мощные инструкции CISC, добавленные в набор инструкций) P = NP, и с некоторыми другими модификациями P ≠ NP. См. Также это сообщение в блоге для прекрасного объяснения релятивизации.

  • естественный , свойство нескольких классических схемных доказательств, доказательств,

  • или алгоритмов , обобщение релятивизации.

15
ответ дан 30 November 2019 в 09:58
поделиться

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

0
ответ дан 30 November 2019 в 09:58
поделиться

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

Перечислить все программы. В раунде i запустите все программы с номерами менее i для одного шага. Если программа завершается удовлетворяющий входу в формулу , вернуть 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 (poly (N)) + O (poly (N)) ^ 2

раундов после того, как он достигнет рассматриваемой программы. . Таким образом, симуляция грубой силы выполняется за полиномиальное время!

(Обратите внимание, что k экспоненциально зависит от размера программы; этот подход на самом деле неосуществим,

1
ответ дан 30 November 2019 в 09:58
поделиться

Самый простой способ - доказать, что существует решение за полиномиальное время для задач в классе NP-полных. Это проблемы, которые находятся в NP и могут быть сведены к одной из известных проблем np. Это означает, что вы могли бы предложить более быстрый алгоритм для доказательства исходной проблемы, поставленной Стивеном Куком или многими другими, которые также оказались NP-завершенными. См. Основополагающую статью Ричарда Карпа и эту книгу для более интересных задач. Было показано, что если вы решите одну из этих задач, весь класс сложности разрушится. изменить: я должен добавить, что я разговаривал со своим другом, который изучает квантовые вычисления. Хотя я понятия не имел, что это значит, он сказал, что определенное доказательство / эксперимент? в квантовом мире можно сделать весь класс сложности, я имею в виду все это, спорный. Если кто-то из присутствующих знает об этом больше, пожалуйста, ответьте.

Были также многочисленные попытки решить проблему без предоставления формального алгоритма. Вы можете попробовать посчитать набор. Есть доказательство Роберта / Сеймора. Люди также пытались решить эту проблему, используя проверенное доказательство диагонализации (также используемое, чтобы показать, что есть проблемы, которые вы никогда не сможете решить). Разборов также показал, что при наличии односторонних функций никакое доказательство не может дать разрешения. Это означает, что для решения этого вопроса потребуются новые методы.

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

Существует отличный обзор, который должен ответить на большинство ваших вопросов: http: / /www.scottaaronson.com/papers/pnp.pdf .

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

Существует отличный обзор, который должен ответить на большинство ваших вопросов: http: / /www.scottaaronson.com/papers/pnp.pdf .

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

Существует отличный обзор, который должен ответить на большинство ваших вопросов: http: / /www.scottaaronson.com/papers/pnp.pdf .

scottaaronson.com/papers/pnp.pdf .

scottaaronson.com/papers/pnp.pdf .

3
ответ дан 30 November 2019 в 09:58
поделиться

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

1
ответ дан 30 November 2019 в 09:58
поделиться

Конечно, описательное доказательство наиболее полезны, но есть и другие категории доказательств: можно, например, предоставить «доказательства существования», которые демонстрируют, что возможно найти ответ, не найдя (или, иногда, даже не предложив как найти) этот ответ.

2
ответ дан 30 November 2019 в 09:58
поделиться

Скорее всего, это будет почти точно так же, как одно из этих

2
ответ дан 30 November 2019 в 09:58
поделиться

Установить N равным мультипликативному тождеству. Тогда NP = P. QED. ; -)

3
ответ дан 30 November 2019 в 09:58
поделиться

Вероятно, это было бы в форме редукции от проблемы NP к проблеме P. См. Страницу в Википедии о сокращениях .

ИЛИ

Как это доказательство , предложенное Виней Деолаликаром.

4
ответ дан 30 November 2019 в 09:58
поделиться

Это может не быть связано с P и NP прямым способом ... Многие теоремы теперь основаны на P! = NP, поэтому доказательство того, что один предполагаемый факт не соответствует действительности, будет иметь большое значение. IIRC даже доказательства чего-то вроде приближения постоянного отношения для TS должно быть достаточно. Я думаю, существование NPI (GI) и других наборов также основано на P! = NP, поэтому приравнивание любого из них к P или NP может полностью изменить ситуацию.

ИМХО все сейчас происходит на очень абстрактном уровне. Если кто-то что-то доказывает о P = /! = NP, это не обязательно должно упоминать ни один из этих наборов или даже конкретную проблему.

4
ответ дан 30 November 2019 в 09:58
поделиться

Назовите меня пессимистом, но это будет так:

...

∴, P ≠ NP

QED

16
ответ дан 30 November 2019 в 09:58
поделиться

Это могло бы принять форму демонстрации того, что предположение, что P ≠ NP приводит к противоречию.

5
ответ дан 30 November 2019 в 09:58
поделиться
Другие вопросы по тегам:

Похожие вопросы: