Последствия недоказуемости

22

Я читал « Является ли P против NP формально независимым? », Но я был озадачен.

В теории сложности широко распространено мнение, что . Мой вопрос о том, что, если это не доказуемо (скажем, в ). (Предположим, что мы только узнаем, что не зависит от но никакой дополнительной информации о том, как это доказано, нет.) $\mathsf{P} \neq \mathsf{NP}$ $ZFC$ $\mathsf{P} \neq \mathsf{NP}$ $ZFC$

Каковы будут последствия этого заявления? Более конкретно,

твердость

Предполагая , что захват эффективные алгоритмы ( Кобам-Эдмондс тезис ) и , мы докажем результаты означают , что они находятся за пределами настоящего досягаемости наших эффективных алгоритмов. Если мы докажем разделение, означает, что не существует алгоритма полиномиального времени. Но что делает $\mathsf{P}$ $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NP\text{-}hardness }$ $\mathsf{NP\text{-}hardness}$ результат среднийесли разделение не доказуемо? Что будет с этими результатами? $\mathsf{NP\text{-}hardness }$

эффективные алгоритмы

Означает ли недоказуемость разделения, что нам нужно изменить наше определение эффективных алгоритмов?

cc.complexity-theory np-hardness big-picture proofs p-vs-np Картик
источник

13

Первое, что вам нужно спросить: формально не зависит от чего? В математической логике есть много наборов аксиом, которые люди рассмотрели. По умолчанию используется ZFC, или теория множеств Цермело-Френкеля с Аксиомой Выбора. Что значит быть независимым от ZFC, так это то, что ни P = NP, ни P! = NP не могут быть доказаны из этих аксиом.

Питер Шор

2

Если вы хотите знать, как выглядит доказательство утверждения вида «независимо от того, является ли X независимым от аксиоматической системы Y», почему бы вам просто не прочитать некоторые примеры? Независимость аксиомы выбора от теории множеств Цермело-Френкеля является известным примером. Я проголосовал за закрытие, как за ненормальный вопрос, но я хотел проголосовать за закрытие темы.

Цуёси Ито

15

Вы читали очень хорошую и свободно доступную статью Скотта Ааронсона; "Является ли P против NP формально независимым?" ( scottaaronson.com/papers/pnp.pdf )

Марцио Де Биаси

2

Вопрос "если X доказано независимо от ZFC, и у нас есть некоторые теоремы вида X

Y, что происходит с этими теоремами?" кажется корректным, и это вопрос, который, как я полагаю, задает ОП. Казалось бы, ответ таков: в некоторых аксиомных системах, таких как ZFC + X, мы держим Y, тогда как в ZFC +

X у нас нет информации о Y. Таким образом, эти условные теоремы все равно будут иметь некоторое значение. Фактически, они имели бы большую ценность в этой ситуации, чем если бы

была доказана как теорема.

\to

$\rightarrow$

\neg

$\lnot$

\neg

$\lnot$

Андрас Саламон

2

Недоказуемость ZFC P против NP, вероятно, будет иметь гораздо большее значение для теории множеств, чем теория сложности.

Дэвид Харрис

18

Ваш вопрос лучше сформулировать так: «Как на теорию сложности повлияет открытие доказательства того, что P = NP формально не зависит от какой-то сильной аксиоматической системы?»

Немного сложно ответить на этот вопрос абстрактно, т. Е. В отсутствие подробностей доказательства. Как упоминает Ааронсон в своей статье, для доказательства независимости P = NP потребуются радикально новые идеи, не только о теории сложности, но и о том, как доказать независимость. Как мы можем предсказать последствия радикального прорыва, о форме которого мы сейчас даже не догадываемся?

Тем не менее, есть пара наблюдений, которые мы можем сделать. В результате доказательства независимости гипотезы континуума от ZFC (и позже от ZFC + больших кардиналов) значительное число людей пришло к точке зрения, что гипотеза континуума не является ни истинной, ни ложной . Мы могли бы спросить, придут ли люди аналогичным образом к выводу, что P = NP является «ни истинным, ни ложным» после доказательства независимости (в качестве аргумента, давайте предположим, что P = NP доказано независимым от ZFC + любой большой основная аксиома). Мое предположение нет. Ааронсон в основном говорит, что он не будет. Вторая теорема Гёделя о неполноте не привела никого, о ком я знаю, к утверждению, что «ZFC непротиворечив» не является ни истиной, ни ложью.утверждение, и у большинства людей есть сильная интуиция, что арифметические утверждения - или, по крайней мере, такие простые арифметические утверждения, как "P = NP" - должны быть либо истинными, либо ложными. Доказательство независимости было бы просто истолковано как говорящее, что у нас нет никакого способа определить, какой из P = NP и P NP имеет место. $\ne$

Можно также спросить, будут ли люди интерпретировать такое положение дел, говоря нам, что с нашими определениями P и NP что-то не так. Возможно, нам следует затем переделать основы теории сложности новыми определениями, с которыми более удобно работать? На данный момент я думаю, что мы находимся в области диких и бесплодных спекуляций, где мы пытаемся пересечь мосты, которые мы еще не достигли, и пытаемся исправить вещи, которые еще не сломаны. Кроме того, это даже не ясно , что ничего быбыть "сломанным" в этом сценарии. Теоретики множеств совершенно счастливы, принимая любые большие кардинальные аксиомы, которые они считают удобными. Точно так же теоретики сложности могут также в этом гипотетическом мире будущего быть совершенно счастливыми, принимая любые аксиомы разделения, которые, по их мнению, верны, даже если они доказуемо недоказуемы.

Короче говоря, ничего не следует логически из доказательства независимости P = NP. Лицо теории сложности может радикально измениться в свете такого фантастического прорыва, но нам просто нужно подождать и посмотреть, как выглядит прорыв.

Тимоти Чоу
источник

3

@vzn: Ваши примеры не просто арифметичны; они, несомненно, арифметические. Но я не уверен, в чем ваша точка зрения. Возьмем некоторое диофантово уравнение

со свойством, что «

не имеет решений» неразрешимо в ZFC. Я хочу сказать, что все, кого я знаю, считают, что либо у

есть решения, либо нет, и что мы просто не можем доказать это так или иначе. Считаете ли вы, что нет факта о том, есть ли у

решения - что

не имеет и не имеет решений?

E

$E$

E

$E$

E

$E$

E

$E$

E

$E$

Тимоти Чоу

4

@vzn: я думаю, что вы полностью упускаете суть. Вопрос не в том, является ли конкретное утверждение неразрешимым , а в том, является ли оно ни истинным, ни ложным . Два понятия совершенно разные. Скажете ли вы, например, что ZFC не является ни последовательным, ни непоследовательным? Все, кого я знаю, считают, что либо ZFC является последовательным, либо нет, даже если у нас нет возможности определить, в каком случае это происходит.

Тимоти Чоу

3

«для меня это звучит как религия, а не математика» - добро пожаловать в метаматематику. Возможно, менее спорным способом сказать «X не является ни истиной, ни ложью» является то, что у нас нет априорной причины предпочитать аксиоматическую систему, в которой X истинно, а не аксиоматическую систему, в которой X ложно. У нас есть (почти) универсально согласованная стандартная модель арифметики; как социальное соглашение, мы принимаем арифметические утверждения, которые в этой модели считаются действительно, действительно верными. То же самое нельзя сказать о теории множеств.

Джефф

2

См. Также consc.net/notes/continuum.html и mathoverflow.net/questions/14338/… - Персональная смесь формализма, платонизма и интуиционизма каждого математика по сути является религиозным убеждением.

Джефф

2

@vzn: Вы все еще упускаете суть. Даже если мы дадим вам ваши личные религиозные убеждения, все, что вы говорите, это то, что вы не присоединились бы к Ааронсону и остальному миру, объявляя арифметические предложения либо истинными, либо ложными. Мы все согласны с тем, что по форме заявления невозможно определить, является ли оно неразрешимым , но это не утверждение. Утверждается, что почти у всех, кроме вас , есть сильная интуиция, что арифметические утверждения являются либо истинными, либо ложными . То, что вы не разделяете это убеждение, не означает, что у других его нет.

Тимоти Чоу

11

Это верный вопрос, хотя, к сожалению, он немного сформулирован. Лучший ответ, который я могу дать, это ссылка:

Скотт Ааронсон: Является ли P против NP формально независимым . Бюллетень Европейской ассоциации теоретической информатики, 2003, вып. 81, стр. 109-136.

Аннотация: Это опрос по поводу заглавного вопроса, написанный для людей, которые (как и автор) считают логику запретной, эзотерической и далекой от своих обычных забот. Начиная с ускоренного курса по теории множеств Цермело Френкеля, он обсуждает независимость оракула; естественные доказательства; результаты независимости Разборова, Раза, ДеМилло-Липтона, Сазанова и др .; и препятствия для доказательства P против NP независимо от сильных логических теорий. Это заканчивается некоторыми философскими размышлениями о том, когда следует ожидать определенного ответа на математический вопрос.

Андрей Бауэр
источник

2

Я полностью упустил тот факт, что статья Ааронсона уже упоминалась в комментариях. Мои извенения.

Андрей Бауэр

7

$[ZFC][1]$ , Это просто означает, что теория не может доказать ни утверждение, ни его отрицание. Это не означает, что утверждение не имеет значения истинности, это не означает, что мы не можем знать значение истинности утверждения, мы могли бы добавить новые разумные аксиомы, которые сделают теорию достаточно сильной, чтобы доказать утверждения или его отрицание. В конце концов, доказуемость в теории - это формальное абстрактное понятие. Это связано с нашим опытом в реальном мире только в качестве модели.

$\mathsf{P}$

$\Sigma_1$ $\Pi_1$ Топология через логику ", 1996.)

$\mathsf{P} \neq \mathsf{NP}$ $\Sigma_2$ и искать сообщения в списке рассылки FOM .

Кава
источник

4

Как доказано в этой статье:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Если можно показать, что P! = NP не зависит от арифметики Пеано, то NP имеет предельно-близкие к полиномиальным детерминированные верхние границы времени. В частности, в таком случае существует алгоритм DTIME (n ^ 1og * (n)), который правильно вычисляет SAT на бесконечно большом количестве огромных интервалов входных длин.

Ави Тал
источник

0

Просто несколько бессвязных мыслей по этому поводу. Не стесняйтесь критиковать.

Пусть Q = [не может доказать (P = NP) и не может доказать (P / = NP)]. Предположим, что Q противоречие. Я также предполагаю, что все известные открытия о P против NP все еще жизнеспособны. В частности, все задачи NP эквивалентны в том смысле, что если вы можете решить одну из них за полиномиальное время, вы можете решить все другие за полиномиальное время. Итак, пусть W будет NP-полной проблемой; W одинаково представляет все проблемы в NP. Из-за Q невозможно получить алгоритм A для решения W за полиномиальное время. В противном случае мы имеем доказательство того, что P = NP, что противоречит Q (1) (*). Обратите внимание, что все алгоритмы вычислимы по определению. То, что A не может существовать, означает, что нет способа вычислить W за полиномиальное время. Но это противоречит Q (2). Нам осталось либо отклонить (1), либо отклонить (2). Любой случай приводит к осуждению. Таким образом, Q является противоречием,

(*) Вы можете сказать: «Ага! Может существовать, но мы просто не можем его найти». Что ж, если A существует, мы можем перечислить все программы, чтобы найти A, перечисляя меньшие и большие программы, начиная с пустой программы. A должен быть конечным, потому что это алгоритм, поэтому, если A существует, то программа перечисления, чтобы найти его, должна завершиться.

Томас Эдинг
источник

1

@Victor: Хороший вопрос. Я предполагаю, что если A существует, то можно просто проанализировать каждую перечисленную программу, чтобы увидеть, действительно ли она решает NP-полную задачу за полиномиальное время. Я полагаю, что поскольку человек работает с конечным набором инструкций (данных каким-то универсальным компьютером), то можно идентифицировать А. Но я не эксперт.

Томас Эдинг

1

Проблема в том, что если Q истинно, то мы попадаем в случай, когда никто, независимо от того, насколько он умен, не может доказать, что определенный алгоритм X, сгенерированный перечислителем, решает P = NP, даже если это так. Т.е. в этом случае алгоритм определения, существует ли P = NP и существует ли он, но невозможно аналитически доказать его правильность. Далее утверждение типа "решает ли алгоритм X проблему P = NP?" звучит очень неразрешимо.

Виктор Стафуса

1

Также ... Если A существует, то пусть N будет размером A. Пусть T будет множеством всех программ размером <= N. Можно одновременно запустить W на всех A 'в T. По мере того как каждая A' завершается, запускаем вывод O через программу, которая проверяет, решает ли O W. (Обратите внимание, что любое так называемое «решение» проблемы NP с полным выполнением может быть проверено за полиномиальное время.) Если O - правильный ответ, отключите все остальные компьютеры. и вернуть O. Имейте в виду, что не каждый A 'должен завершаться, потому что A является одним из них и выдаст правильный O за полиномиальное время. Таким образом, не нужно даже доказывать, что A решает P = NP. N существует по определению.

Томас Эдинг

1

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

Виктор Стафуса

3

«P = NP не зависит от ZFC» - это не то же самое, что «мы не можем найти алгоритм для решения любой проблемы в NP в детерминированный полиномиальный момент времени», как отметил Виктор. Точные определения этих классов весьма важны при рассмотрении таких понятий, как независимость от теории.

Андрас Саламон

Последствия недоказуемости

твердость

эффективные алгоритмы

Ответы: