Algoritma yang menjalankan waktu tergantung pada P vs NP

Adakah yang diketahui, contoh eksplisit dari suatu algoritma dengan properti sedemikian sehingga jika maka algoritma ini tidak berjalan dalam waktu polinomial dan jika maka ia berjalan dalam waktu polinomial?$P\neq NP$$P=NP$

Jika Anda berasumsi bahwa dapat dibuktikan dalam PA (atau ZFC), contoh sepele adalah sebagai berikut:$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

Contoh lain - kurang sepele - yang tidak bergantung pada asumsi adalah sebagai berikut:

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.

Jika $P =NP$ algoritme akan segera atau lambat - misalkan pada input $x_0$ - cari indeks waktu polinomial mesin Turing (atau versi empuknya) $M_{SAT}$ yang memecahkan SAT dalam $O( |x| ^ { |M_{SAT}| })$ dan untuk semua input yang lebih besar dari $x_0$ akan terus mensimulasikan dan menghentikannya dalam waktu polinomial (perhatikan bahwa langkah 2 juga dapat diperiksa dalam waktu polinomial). Dengan kata lain jika $P = NP$ Algoritma memecahkan SAT dalam waktu polinomial pada semua kecuali sejumlah contoh.

Jika $P \neq NP$ algoritme berjalan dalam waktu eksponensial.