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

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

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

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

Спасибо.

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

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

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

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

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

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

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

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

Доказательство того, что 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