Алгоритм, время работы которого зависит от P против NP

18

Существует ли известный явный пример алгоритма со свойством, состоящим в том, что если то этот алгоритм не выполняется за полиномиальное время, а если то он выполняется за полиномиальное время?пNппзнак равноNп

user2925716
источник
9
Вроде. Если P = NP, универсальный алгоритм поиска Левина работает за полиномиальное время при приеме экземпляров en.wikipedia.org/wiki/…
Эмиль Йержабек поддерживает Монику
@Emil: если P = NP, то также P = coNP, так что вы не можете одновременно выполнять поиск Левина на дополнении к вашему языку, таким образом предоставляя действительно много времени алгоритм во всех случаях?
Джошуа Грохов
3
@JoshuaGrochow Для того, чтобы выразить язык как coNP, мне нужно было бы сначала знать алгоритм polytime для NP, побеждающий всю цель.
Эмиль Йержабек поддерживает Монику

Ответы:

17

Если вы предполагаете, что доказуемо в PA (или ZFC), тривиальным примером является следующий:пзнак равно?Nп

Input: N   (integer in binary format)
For I = 1 to N do
begin
  if I is a valid encoding of a proof of P = NP in PA (or ZFC)
    then halt and accept
End
Reject

Другой, менее тривиальный пример, который не предполагает никаких предположений, заключается в следующем:

Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration] 
  2) and  M_i solves SAT correctly 
       on all formulas |y| < log(log(|x|))
          halting in no more than |y|^|M_i| steps
          [ checkable in polynomial time w.r.t. |x| ]
  if such i exists simulate M_i on input x 
      until it stops and accept/reject according to its output
      or until it reaches 2^|x| steps and in this case reject;
  if such i doesn't exist loop for 2^|x| steps and reject.

Если алгоритм рано или поздно - предположим, на входе - найдет индекс машины Тьюринга за полиномиальное время (или его дополненную версию) которая решает SAT в и для всех входов, больше чем , продолжит моделировать его и остановится за полиномиальное время (обратите внимание, что шаг 2 также можно проверить за полиномиальное время). Другими словами, если P = N P, алгоритм решает SAT за полиномиальное время на всех, кроме конечного числа экземпляров.пзнак равноNпИкс0MSATО(|Икс||MSAT|)Икс0пзнак равноNп

Если пNп алгоритм работает за экспоненциальное время.

Марцио де Биаси
источник
Как мне быстро решить, является ли «I допустимой кодировкой доказательства P = NP в PA (или ZFC)»?
user2925716
я
2
Высокое предположение.
Джирка Ханика
1
Если P ≠ NP, время выполнения безусловного алгоритма является суперполиномиальным (в соответствии с запросом), но если NP является лишь слегка суперполиномиальным, а не экспоненциальным. Мы можем изменить алгоритм, сделав его экспоненциальным, но доказательно сделав его экспоненциальным (в отличие от просто экспоненциального), если P ≠ NP, вероятно, так же сложно, как решить P = NP.
Дмитрий Тарановский
1
Икс|Mя|2Икс