Algorytm, którego czas działania zależy od P vs. NP

18

Czy istnieje znany, wyraźny przykład algorytmu o takiej właściwości, że jeśli to ten algorytm nie działa w czasie wielomianowym, a jeśli to działa w czasie wielomianowym?PNPP=NP

użytkownik2925716
źródło
9
Raczej. Jeśli P = NP, uniwersalny algorytm wyszukiwania Levina działa w czasie wielomianowym po zaakceptowaniu instancji en.wikipedia.org/wiki/…
Emil Jeřábek obsługuje Monikę
@Emil: jeśli P = NP, to także P = coNP, więc czy nie możesz jednocześnie wyszukiwać Levin na dopełnieniu swojego języka, dając w ten sposób prawdziwie poli-czasowy algorytm we wszystkich instancjach?
Joshua Grochow
3
@JoshuaGrochow Aby wyrazić język jako coNP, musiałbym najpierw poznać algorytm czasu policy dla NP, pokonując cały cel.
Emil Jeřábek wspiera Monikę

Odpowiedzi:

17

Jeśli założysz, że można udowodnić w PA (lub ZFC), trywialny przykład jest następujący:P=?NP

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

Kolejny - mniej trywialny - przykład, który nie opiera się na żadnym założeniu, jest następujący:

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.

Jeśli algorytm prędzej czy później - przypuśćmy, że na wejściu - znajdzie indeks wielomianowego czasu maszyny Turinga (lub jego wersji wyściełanej)P=NPx0MSAT która rozwiązuje SAT w O(|x||M.S.ZAT.|) i dla wszystkich danych wejściowych większych niż x0 będzie nadal symulować i zatrzymywać się w czasie wielomianowym (zwróć uwagę, że krok 2 można również sprawdzić w czasie wielomianowym). Innymi słowy, jeśli P.=N.P. algorytm rozwiązuje SAT w czasie wielomianowym we wszystkich przypadkach oprócz skończonej liczby instancji.

Jeśli P.N.P. algorytm działa w czasie wykładniczym.

Marzio De Biasi
źródło
Jak szybko zdecydować, czy „Jestem prawidłowym kodowaniem dowodu P = NP w PA (lub ZFC)”?
user2925716,
ja
2
Wysokie założenie.
Jirka Hanika,
1
Jeśli P ≠ NP, czas działania bezwarunkowego algorytmu jest super wielomianowy (zgodnie z żądaniem), ale jeśli NP jest tylko bardzo nieznacznie wielobiegunowy, a nie wykładniczy. Możemy zmienić algorytm, aby uczynić go wykładniczym, ale możliwe, że sprawi, że będzie wykładniczy (w przeciwieństwie do tylko io-wykładniczego), jeśli P ≠ NP jest tak trudne, jak rozwiązanie P = NP.
Dmytro Taranovsky
1
x|M.ja|2)x