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

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?$P\neq NP$$P=NP$

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 =NP$$x_0$$M_{SAT}$ która rozwiązuje SAT w $O( |x| ^ { |M_{SAT}| })$ i dla wszystkich danych wejściowych większych niż $x_0$ 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 = NP$ algorytm rozwiązuje SAT w czasie wielomianowym we wszystkich przypadkach oprócz skończonej liczby instancji.

Jeśli $P \neq NP$ algorytm działa w czasie wykładniczym.