Как доказать P

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

Мы можем показать, что P NP$=$ тогда и только тогда, когда сможем разработать алгоритм, который решает любой конкретный случай проблемы в NP за полиномиальное время.

Однако я не понимаю, как на земле мы можем доказать, что P NP . Пожалуйста, извините меня за следующее подобие, поскольку оно может быть настолько неуместным, но говорить кому-то, чтобы он доказывал, что P не равен NP, мне кажется, что я говорю кому-то, чтобы доказать, что Бога не существует.$\neq$

Существует ряд проблем, которые не могут быть решены с помощью недетерминированных конечных автоматов (NFA) с полиномиальным числом состояний независимо от текущей технологии (я знаю, что это неаккуратное определение). Кроме того, у нас есть достаточно большой набор алгоритмов, который создает некоторые важные проблемы (кратчайший путь, минимальное остовное дерево и даже сумма целых чисел ) для задач полиномиального времени.$1 + 2 + \dots + n$

Мой вопрос вкратце: если я верю, что P NP$=$ ≠ , вы скажете: «Тогда покажите свой алгоритм, который решает проблему NP за полиномиальное время!». Предположим, что я верю P NP . Тогда что бы вы спросили? Что бы вы хотели, чтобы я показал?$\neq$

Ответ явно "ваше доказательство". Однако какое доказательство показывает, что алгоритм не может существовать? (в этом случае алгоритм полиномиального времени для задачи NP )

Есть три основных способа, которые я знаю, которые могут доказать, что P NP$\,\neq\,$ .

1. Показано , что есть некоторая проблема , которая находится в  NP , но не в  P . Вы, вероятно, знакомы с доказательством того, что для сортировки на основе сравнения требуется время для сортировки списка из  элементов. В принципе, можно получить аналогичное доказательство, показывающее, что 3SAT или некоторая другая NP- полная задача не может быть решена за время для любой константы  . Теория геометрической сложности стремится использовать инструменты из алгебраической геометрии и теории представлений групп для доказательства таких нижних границ, рассматривая симметрии, которыми обладают проблемы. Сложность схемы это другое.n O ( n c ) $\Omega(n\log n)$$n$$O(n^c)$$c$

2. Показано, что P и  NP имеют разные структурные свойства. Например, P  закрыто при дополнении. Если бы вы могли показать, что NP co-NP$\,\neq\,$ (то есть, что NP  не замкнут при дополнении), то это должно быть то, что P NP$\,\neq\,$ . Конечно, это всего лишь подталкивает проблему на один уровень глубже - как бы вы доказали, что NP co-NP$\,\neq\,$ ?

   Другая возможность состоит в том, что мы знаем, что NP  - это именно тот класс задач, который может быть определен в так называемой экзистенциальной логике второго порядка. Если можно показать, что нет логики, точно соответствующей  P (или если есть логика, но она отличается от ), то P и  NP должны отличаться. Связанная (фактически эквивалентная) идея состоит в том, чтобы показать, что у P  нет полных проблем при редукциях, определенных логикой первого порядка, поскольку известно, что у NP  есть полные проблемы при этих редукциях.$\exists\mathrm{SO}$

3. Докажите, что какая-то проблема не является NP- неполной. Если P NP$\,=\,$ , то каждая нетривиальная задача в  NP является NP -полной при многократном сокращении за полиномиальное время («нетривиальный» здесь означает не или  ). Итак, если вы можете показать, что какая-то проблема в  NP не является NP- полной, то мы должны иметь P NP .Σ $\emptyset$$\Sigma^*$ $\,\neq\,$

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

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

Предположим, что я верю P ≠ NP . Тогда что бы вы спросили? Что бы вы хотели, чтобы я показал?

Сначала попытайтесь объяснить «почему» P ≠ NP и почему эту причину можно использовать для доказательства P ≠ NP в подходящей логической структуре. Затем нарисуйте доказательство и объясните, как можно защитить его самые сомнительные части. Затем разбейте это доказательство на более простые утверждения, которые можно проверить независимо.

• Например, логическая структура, предоставляемая ZFC, хороша (даже слишком хороша в определенном смысле) для доказательства существования моделей (явно заданных наборов аксиом, часто даже удовлетворяющих дополнительным металогическим свойствам). Поэтому, если вам известна причина, по которой P ≠ NP связана с существованием модели с некоторыми странными свойствами, сначала объясните эту причину, а затем покажите, как можно построить соответствующую модель в ZFC.
• В качестве примера, я полагаю, что одной из причин «почему» P ≠ NP является то, что математика может приближаться почти ко всему, что происходит в физическом мире, включая случайность. Однако известно, что формальные системы очень ограничены в своей способности доказать, что данная строка, число, «объект» или «артефакт» являются по существу случайными, поэтому маловероятно, что эту причину можно использовать для доказательства в любой явно заданной детерминированной формальной системе. Возможно, если вы спроектировали вероятностную (квантовую) систему доказательств, в которой вы могли бы проверять определенные доказательства в системе только до конечной вероятности в зависимости от имеющихся у вас физических ресурсов ...
• Как вероятный не пример, закон исключенной середины в основном отражает статическое представление о (математической) вселенной и, следовательно, крайне маловероятно, чтобы иметь место в динамической вселенной. Теперь NP = coNP (или любой другой коллапс полиномиальной иерархии) будет в основном приближенной версией закона исключенного среднего в отношении сложности времени, но сложность времени слишком близка к динамической вселенной, чтобы это было возможно. Существуют логические структуры, такие как линейная логика Жирара, которые способны улавливать динамические аспекты вселенной, поэтому ... Обратите внимание, что Брауэр был в подобной ситуации и уже заявил о необходимом провале программы Гильберта как факт в своем вступительном слове « Интуиционизм и формализм». в 1912 году (объясняя, почему это будет круговое рассуждение), но все же не смог даже набросать доказательство неполноты Геделя с 1930 года.
• В качестве приблизительного примера, давайте попробуем собрать некоторые из доступных доказательств для P ≠ NP , а именно экспоненциальную нижнюю границу для многогранника коммивояжера и неразрешимость процедур, основанных на разрешении, для выполнимости из-за слабых принципов воронки., «Почему» в этом случае состоит в том, что определенный класс NP-полных задач не может быть эффективно решен с помощью алгоритмов, основанных на определенных естественных (для рассматриваемого класса NP-полных задач) принципах, таких как формулировки линейного программирования для TSP или на основе разрешения методы доказательства для SAT. Разные статьи приводили разные независимые причины, по которым это можно было бы доказать, например, в последней статье о TSP в качестве причины упоминалась «тесная связь между полуопределенными переформулировками программирования LP и односторонними квантовыми протоколами связи», а в последней статье о разрешении привел две независимые причины, а именно нижние оценки "для класса формул, представляющих принцип голубиных отверстий, и для случайно сгенерированных формул".
  Вы также можете заметить, что были попытки усилить результаты с течением времени. Первоначальные результаты для TSP касались только симметричной формулировки линейного программирования, в то время как последние результаты не имеют такого ограничения, а также применяются к задачам максимального разреза и максимального стабильного набора в дополнение к TSP. Первоначальные результаты для разрешения рассматривали только основные процедуры разрешения Дэвиса-Путнэма и один класс искусственных контрпримеров, в то время как последние результаты охватывают большие классы методов, основанных на разрешении, и дают множество классов встречающихся в природе контрпримеров.
  Что касается TSP, я понятия не имею, как следует усиливать результаты, за исключением, может быть, применения к большему количеству задач в дополнение к TSP, максимальному сокращению и максимальному стабильному набору. Для решения, у меня было бы много идей, как улучшить результаты дальше, но статья, на которую я ссылался, в 2002 году, Стивен Кук и Фуонг Нгуен опубликовали монографию « Логические основы сложности доказательств» в 2010 году, которую я даже не просматривал, и я думаю, это уже охватит многие мои идеи. Интересно отметить, насколько мало на самом деле имеет значение для большинства из нас, насколько эти результаты были усилены с течением времени, несмотря на наш интерес к P ≠ NP.вопрос. Даже если бы тем временем было доказано, что алгоритмы, основанные на логических системах без эквивалента правила разреза, не могут эффективно решать проблемы выполнимости, мы все равно считаем, что в P ≠ NP не было никакого существенного прогресса , что проблема по существу по-прежнему широко открыт, как никогда.