Доказательство Сложность доказательства или несоответствия P = NP

15

Проводились ли какие-либо исследования сложности доказательства решения проблемы P = NP? Если нет, учитывая отсутствие прогресса в решении этой проблемы, было бы неразумно предполагать, что любое доказательство, которое решает проблему P = NP, потребует суперполиномиального числа шагов?

Тони Джонсон
источник
18
Может быть, я не понимаю ваш вопрос, но любое разрешение P против NP будет подтверждением постоянного размера, да?
Курт Мюллер
@ Курт Мюллер. Для доказательства потребуется суперполиномиальное количество шагов, основанное на количестве символов, необходимых для кодирования задачи P = NP.
Тони Джонсон
1
@TonyJohnson Суперполином по константе все еще остается константой.
Дэвид Ричерби

Ответы:

14

Известно, что любое доказательство нижних границ суперполиномиальной схемы (которые являются несколько более сильными утверждениями, чем ) требует суперполиномиальных, даже экспоненциальных размерных доказательств в слабых системах доказательств, таких как разрешение. Обобщение этого для более сильных систем доказательств является хорошо известной открытой проблемой.пNп

См. Раздел 5 этого опроса А. Разборова, где эти вещи показаны.

Ян Йоханнсен
источник
24

Сложность доказательства имеет смысл только тогда, когда существует последовательность операторов, зависящая от параметра . Например, в предложении P H P n (неформально) говорится, что нет биекции [ n + 1 ] [ n ] . Эта последовательность предложений трудна для некоторых систем доказательственного предложения.NпЧАСпN[N+1][N]

Утверждение является единым утверждением, поэтому вы не можете применить к нему сложность доказательства напрямую. Однако следующая последовательность операторов имеет смысл для конкретных функций s ( n ) : «нет схемы размера s ( n ), правильно решающей SAT для экземпляров длины n ». Это было рассмотрено в литературе, например, Разборовым (который рассматривал установку равномерной сложности доказательства, то есть ограниченной арифметики).пNпs(N)s(N)N

Юваль Фильмус
источник
5

У нас есть 3 случая:

  • Там существует доказательство того, что . Тогда существует алгоритм, решающий задачу «Извлеките доказательство того, что P = N P », который выполняется за O ( 1 ) времени. Он жестко кодирует доказательство в самой машине Тьюринга и генерирует его. Он работает в одно и то же время независимо от его ввода.пзнак равноNппзнак равноNпО(1)

  • Аналогично, если существует доказательство того, что , то мы можем написать алгоритм, испускающий это доказательство за O ( 1 ) раз.пNпО(1)

  • Если не существует доказательств того или иного случая, то минимальная сложность поиска доказательства для любого из них - это : ни одна машина Тьюринга не может остановить и выдать доказательство того или другого, поскольку таких доказательств не существует.О()

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

Точнее, мы не можем точно знать, насколько сложно найти доказательство или обратное, пока не узнаем результат, который побеждает точку.пзнак равноNп

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

jmite
источник
-2

Если P = NP, то все, что вам нужно сделать, это создать алгоритм полиномиального времени для решения некоторой NP-полной задачи и доказать, что он действительно полиномиален (что может быть сложно, например, алгоритм Simplex обычно работает очень быстро, но доказывает, что он бежит быстро, кажется невероятно трудным).

N100

gnasher729
источник
пзнак равно?Nп? »
Дэвид Ричерби
Там же (маловероятно , но вполне возможно) результат , что P = NP , но там нет не доказуемо равномерно полиномиальный алгоритм , например , SAT.
Стивен Стадницки