Доказательство P = NP без математических утверждений / компьютерной программы

13

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

Несмотря на это, я хотел бы спросить:

Если человек, который не является ни математиком, ни программистом, должен был предложить блок-схему или серию шагов, написанных на базовом английском языке, которые якобы обеспечивают решение одной из проблем P против NP, это будет считаться «доказательством» того, что P = NP .. для того, чтобы получить приз Института Глин :)? Или это необходимо для написания решения в виде математического доказательства / компьютерной программы?

Спасибо.

Рафаэль
источник
10
Посмотреть эту коллекцию: win.tue.nl/~gwoegi/P-versus-NP.htm . Вы не хотите стать одним из них.
Юваль Фильмус
есть один возможный «слабый» прецедент для этого. Godels thm и диагонализация, возможно, были основаны на парадоксе Ричардса, который был из литературной работы. но обратите внимание, что математикам потребовались очень продвинутые математики, чтобы преобразовать их в законные математические утверждения / свойства.
vzn
@vzn: та самая страница Википедии, на которую вы ссылаетесь, датирует парадокс Ричарда 1905 годом; диагонализация восходит к 1891 году. Таким образом, парадокс Ричарда, скорее всего, основан на диагонализации, а не наоборот.
Ниль де Бёдрап,
@NieldeBeaudrap, vzn: Ваши комментарии превращались в разговор, поэтому я переместил их в чат , пожалуйста, продолжайте там.
Жиль "ТАК - перестань быть злым"

Ответы:

16

«Нет», вы можете использовать «базовый английский».

Если бы вам это удалось, вы бы создали конструктивное доказательство . Доказательства в математике часто представляют собой смесь «базового английского», как вы его называете, и математических формул, но они не должны содержать ни того, ни другого, чтобы быть действительным доказательством.

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

Сделав это, у вас есть математическое доказательство в ваших руках. Так что на самом деле, я должен был сказать « Да » в начале, вам нужно математическое доказательство .

phant0m
источник
14
Давайте не будем давать никому ложных надежд здесь. Крайне маловероятно, что непрофессионал может решить против N P , или что решение может быть выражено в «обычном английском». Есть более полезные вещи для непрофессионала, чем пытаться решить самые сложные математические задачи. пNп
Андрей Бауэр
3
@AndrejBauer Конечно, я не имел в виду, что это вероятно. Я полагаю, что вам понравился бы ответ, похожий на ответ Нила . Но в то время как это дает хорошие перспективы, на самом деле это не решает вопрос, который был задан.
phant0m
3
Я знаю, ты не хотел подразумевать что-либо подобное. Я просто хотел записать явное предупреждение, чтобы журналист или кто-то не прочитал это и не подумал, что против N P будет разрешен литературным критиком. пNп
Андрей Бауэр
@ phant0m: мне любопытно. Мой первый абзац не касается реального вопроса?
Ниль де Бодрап
@NieldeBeaudrap Конечно, это решает проблему, но кажется, что вывод должен быть сделан. Примечание: можно также интерпретировать "Indeed"предложение как объяснение доказательства словами, но само по себе оно не будет доказательством. Кроме того, сама машина Тьюринга не является доказательством, если не дано подтверждение ее правильности. Кроме того, это означает, что представление ТМ над блок-схемой по своей сути является превосходным доказательством, даже если это не так.
phant0m
19

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

Но есть фундаментальная проблема с вопросом, который вы задаете. Что это значит для того, кто мог бы решить P против NP - и, показав, что они равны, не меньше, - на самом деле не быть ни ученым-программистом, ни математиком? Возможно, они не работают профессионально в качестве программиста или математика, но это не относится к делу, если у них есть умение решать то, что некоторые (например, Скотт Ааронсон) называют самой важной математической проблемой, которую мы когда-либо рассматривали. Если кто-то имеет подготовку (или даже самоучку), чтобы успешно решить проблему, а также четко донести решение до другихпутем определения основных подпрограмм и их роли в решении, например, SAT или HAMPATH, то, являются ли они занятыми или даже имеют степени, не имеет значения; тем не менее, в этом случае они математик или ученый. Еще лучше, если они могут описать, как их решения преодолевают классические препятствия, такие как результаты оракула, такие как оракулы A, для которых P ANP A (или наоборот), показывая конкретно, какие структуры в задаче использует алгоритм, который не будет доступно в модели оракула. Проблема, однако, состоит в том, что большинство людей, которые мечтают о решении P против NP как любители или аутсайдерыПохоже, им не хватает коммуникативных навыков для того, чтобы на самом деле адекватно описать свою работу, или (из-за того, что они не читали достаточно), они не знают о результатах, которые сделали бы их подход к решению проблемы обреченным с самого начала.

Как и во всех мечтах о славе в наши дни, существует одна проблема с фантазией о том, чтобы решить Р против NP . Проблема в том, что это почти невозможно. Не на самом деле невозможно, заметьте, или, по крайней мере, не обязательно невозможно; почти так. Как кто-то умный с амбициями, он может упустить из виду тот факт, что есть много других ярких людей: многие из которых также думали о проблеме; и многие из них ярче, чем он сам, даже на пару порядков. И что были такие яркие люди до тех пор, пока проблема была вокруг; и все же это остается нерешенным. Да, в принципе возможно, что все думают об этом не так, и были на протяжении десятилетий. Но разве этодействительно особенно вероятно? Никто не должен ожидать, что он будет единственным человеком, который сможет обнаружить одну ошибку знака, которую делают все остальные, потому что, если все остальные делают эту ошибку, то должно быть что-то в проблеме, которая заставит человека совершить ту же ошибку. Или - в более вероятном случае, если причина, по которой проблема остается нерешенной, нето, что люди продолжают делать простые ошибки или еще не подумали об одном простом трюке, который разрушает все это - то, что делает проблему принципиально сложной, по сути является объективной сложностью проблемы, и никакие умные танцевальные шаги не позволят просто изящно вальсировать преодолеть все препятствия; то, что требуется, - это подход, который является не просто новым, но довольно глубоким, выявляющим тонкие структуры, которые раньше никто не видел. Такая структура, которую можно определить, постоянно думая о проблеме годами.

Если вы хотите быть реалистичными в отношении того, что потребуется для решения проблемы P и NP , вы можете сравнить ее с аналогично известными достижениями за последние несколько десятилетий, такими как доказательства теоремы о четырех цветах, последней теоремы Ферма или Гипотеза Пуанкаре. Когда-нибудь у них могут быть более простые доказательства, но оригинальные доказательства уводят вас далеко в пустыню, чтобы довести вас до конца (или в случае теоремы о четырех цветах маршрут очень длинный и повторяющийся). Нет особой причины подозревать, что P против NP будет отличаться; так что , если в конце концов , это являетсярешенный любителем, очень велики шансы, что это будет кто-то с аналогичными базовыми знаниями и осведомленностью о методах кого-то, кто имеет академическое образование. Любой реалистичный любитель, который мечтает решить P против NP, преуспел бы, чтобы помнить это.

Ниль де Бодрап
источник
2
Хотя все, что вы говорите, правда, я боюсь, что такое мышление (которое стало распространенным в данной области, возможно, в качестве защитного механизма) может обескуражить одного гения-самоучку, который может решить проблему сегодня. Я думаю, что более полезное сообщение звучит так: иди и пройди столько тренировок, сколько нужно, чтобы убедить хотя бы одного профессионала, сначала прочитать свою работу, а затем ее обоснованность. Это может занять годы, но это путь.
Рафаэль
6
@ Рафаэль: Я думаю, что на самом деле мой менталитет идеально приспособлен даже к возможности гения-самоучки. Мое послание гению-самоучке таково: с одной стороны, не будучи академиком, не значит, что вы не математик - и что я бы оценил ответ по его качеству. Таким образом, на этом гении-самоучке лежит обязанность удостовериться, что ответ имеет качество, и остерегаться ловушек, на которые любители часто становятся жертвами.
Ниль де Бодрап,
2
Я боюсь, что это мышление ... может обескуражить одного гения-самоучку, который может решить проблему сегодня. - Хорошо. Вашему гению-самоучке следует напомнить, что планка чрезвычайно высока и что десятки (сотни?) Других гениев-самоучек пытались и не смогли ее достичь.
Джефф
«Последняя теорема Ферма, или гипотеза Пуанкаре. Когда-нибудь у них могут быть более простые доказательства, но оригинальные доказательства уведут вас далеко в пустыню, чтобы привести вас к концу (или в случае теоремы четырех цветов маршрут очень длинный и повторяющийся)». это справедливое / разумное ожидание некоторых, но с другой стороны, в отличие от произвольных теоретических курьезов, таких как FLT и 4CT, можно привести случай, когда доказательство P vs NP может дать (фундаментальные) инструменты для других разделений классов сложности и теории сложности в целом. или даже может быть розеттским камнем или недостающим звеном для дальнейшего продвижения ..
vzn
@vzn: Я не совсем уверен, к чему ты клонишь с этим различием. Тот факт, что P против NP важен, не повышает вероятность того, что найдется простое решение, которое может найти умный, но непосвященный любитель.
Ниль де Бодрап
-5

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

У элитных профессионалов есть более сложные причины, чем то, что многие светлые умы пытались и не смогли построить полиномиальный алгоритм для NP или доказать N! = NP. Тем не менее, они разумно ожидают, что этот аргумент должен быть наиболее убедительным для непрофессионала. Вероятно, они правы в том, что ссылки на барьеры, связанные с релятивизирующими доказательствами, естественными доказательствами или алгебраическими доказательствами, редко бывают убедительными для неэксперта. Если слишком много «любителей» пытаются разрешить P против NP определенным образом (например, с помощью логического решения или сводя его к задаче линейного программирования), то кто-то пройдет через боль (иногда это занимает годы), чтобы доказать, что этот конкретный угол атаки, скорее всего, обречен на провал.

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

Мы можем оставаться агностиками, говоря, что мы просто не знаем, но в науке может быть такая вещь, как слишком большой скептицизм. Например, Скотт Ааронсон однажды заявил, что в других науках P! = NP к настоящему времени был бы объявлен законом природы. Я склонен согласиться. В конце концов, мы пытаемся раскрыть правду о природе вычислений, и этот квест не пойдет быстрее, если мы будем настаивать на том, чтобы отбросить все доказательства, которые не в форме математических доказательств из первых принципов.

Это изменение не предназначено для уменьшения количества отзывов, но чтобы было совершенно ясно, что этот ответ серьезно относится к тому факту, что эксперты «знают, что P! = NP», даже если они не могут это доказать.


23 ноября 2013 г. Еще раз спасибо за все отзывы. Для записи, ответ теперь имеет 7 отрицательных голосов, 1 положительный ответ и 14 комментариев (8 от меня). Из-за количества комментариев, интересные ссылки и обоснования, приведенные в комментариях, скрыты, поэтому я решил добавить некоторые из них здесь:

  • Как писал сам Гёдель фон Нейману, если бы P = NP были верны «для всех практических целей», то его теорема о неполноте была бы верна только в теории, но фактически ложна на практике.

  • В своей статье 1971 года Стивен Кук ... не смог произвести контрпримеры для процедуры Дэвиса-Путнэма (решено Haken 1985). Сегодня доступно много методов, результатов и контрпримеров для «опровержения» предложенных эффективных NP-решателей. Также P = NP противоречит «закону сохранения сложности», «качественному бесконечному <-> количественному конечному» соответствию, ...

  • Давным-давно Скотт Ааронсон написал этот комментарий :

    Аноним: Вы утверждаете (как факт!), что 3SAT - это язык в NP, который не может быть вычислен за полиномиальное время. Но вы не можете доказать это. Это твой научный метод? Да. Как твердый сторонник науки и разума, я стараюсь четко различать, что я могу доказать, и то, что я просто знаю, правда.

  • Скотт известен тем, что пытался продемонстрировать, что это значит, что он «что-то» знает, например, поставив $ 200 000: scottaaronson.com/blog/?p=458

Томас Климпел
источник
2
7
Никто не «знает», что P! = NP. Эксперты могут твердо в это поверить, но ни один эксперт не знает этого (если только у кого-то нет доказательства, и он не сохранил его для себя). Возможно, хотя и маловероятно, что P = NP верно. Как примечание, все (особенно ученые) должны быть открыты для всего, если не доказано иное. В этом случае каждый ученый, каким бы большим он ни был, считает, что P! = NP, должен признать, что существует вероятность того, что P = NP имеет место.
Джордж
7
В математике проблема игнорирования доказательств и слепого продвижения вперед заключается в том, что вы можете предположить что-то неправильное. Это будет сделать квесты идти гораздо медленнее. Физические науки не имеют этой проблемы (за исключением случаев, таких как квантовая гравитация / теория струн), потому что они должны согласиться с экспериментом.
Питер Шор
1
@ThomasKlimpel: Я помню, что опубликовал этот комментарий, но не где. Учитывая, что, на кого бы я ни отвечал (вы?), Просто использовал его как авторитет, чтобы аргументировать правильность математического платонизма, в то время как я после некоторого рассмотрения пришел к позиции формализма, сам факт того, что у Годеля было другое мнение без дальнейшего разработка действительно не имеет значения. Технические аргументы не выигрываются, как теннисные матчи, с быстрым опровержением. Точно так же, убедительные ответы оцениваются не только по их краткости (хотя это помогает), ни по авторитету, но и по их техническим достоинствам.
Ниль де Бодрап,
3