Проводились ли какие-либо исследования сложности доказательства решения проблемы P = NP? Если нет, учитывая отсутствие прогресса в решении этой проблемы, было бы неразумно предполагать, что любое доказательство, которое решает проблему P = NP, потребует суперполиномиального числа шагов?
complexity-theory
np
Тони Джонсон
источник
источник
Ответы:
Известно, что любое доказательство нижних границ суперполиномиальной схемы (которые являются несколько более сильными утверждениями, чем ) требует суперполиномиальных, даже экспоненциальных размерных доказательств в слабых системах доказательств, таких как разрешение. Обобщение этого для более сильных систем доказательств является хорошо известной открытой проблемой.п≠ Nп
См. Раздел 5 этого опроса А. Разборова, где эти вещи показаны.
источник
Сложность доказательства имеет смысл только тогда, когда существует последовательность операторов, зависящая от параметра . Например, в предложении P H P n (неформально) говорится, что нет биекции [ n + 1 ] → [ n ] . Эта последовательность предложений трудна для некоторых систем доказательственного предложения.N P H PN [ n + 1 ] → [ n ]
Утверждение является единым утверждением, поэтому вы не можете применить к нему сложность доказательства напрямую. Однако следующая последовательность операторов имеет смысл для конкретных функций s ( n ) : «нет схемы размера s ( n ), правильно решающей SAT для экземпляров длины n ». Это было рассмотрено в литературе, например, Разборовым (который рассматривал установку равномерной сложности доказательства, то есть ограниченной арифметики).P ≠ N P s ( n ) s ( n ) N
источник
У нас есть 3 случая:
Там существует доказательство того, что . Тогда существует алгоритм, решающий задачу «Извлеките доказательство того, что P = N P », который выполняется за O ( 1 ) времени. Он жестко кодирует доказательство в самой машине Тьюринга и генерирует его. Он работает в одно и то же время независимо от его ввода.п= Nп п= Nп O ( 1 )
Аналогично, если существует доказательство того, что , то мы можем написать алгоритм, испускающий это доказательство за O ( 1 ) раз.п≠ Nп O ( 1 )
Если не существует доказательств того или иного случая, то минимальная сложность поиска доказательства для любого из них - это : ни одна машина Тьюринга не может остановить и выдать доказательство того или другого, поскольку таких доказательств не существует.O ( ∞ )
То, что мы не нашли никаких доказательств, не означает, что их не существует, а классы сложности определены в терминах того, что существует.
Точнее, мы не можем точно знать, насколько сложно найти доказательство или обратное, пока не узнаем результат, который побеждает точку.п= Nп
Что мы знаем, так это то, что в общем проблема «Возьмите утверждение в логике предиката и определите, есть ли для него доказательства», неразрешима. Таким образом, нет никаких общих процедур генерации доказательств, в которые мы можем включить P против NP, которые гарантированно дадут результат.
источник
Если P = NP, то все, что вам нужно сделать, это создать алгоритм полиномиального времени для решения некоторой NP-полной задачи и доказать, что он действительно полиномиален (что может быть сложно, например, алгоритм Simplex обычно работает очень быстро, но доказывает, что он бежит быстро, кажется невероятно трудным).
источник