P = NP Need Not Give a SAT Algorithm

In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs. While I believe this statement is true because P ≠ NP, I would like to argue we won't prove it anytime soon.

Bill links to a TCS Stack Exchange answer by Marzio De Biasi giving a fixed algorithm that would get SAT correct except on a finite number of inputs if P = NP. Here is Marzio's algorithm.

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.

This proof relativizes: There is a fixed relativizing Turing machine M such that for all A, if P^A = NP^A then L(M^A) runs in polynomial time and differs from SAT^A on only a finite number of strings. SAT^A is a relativizable form of SAT with a built in relations that answer whether a sequence of variables encode an string in A. SAT^A is NP^A-complete for all A.

The following shows any proof that a fixed algorithm can compute all of SAT correctly if P = NP cannot relativize.

Theorem: For every deterministic Turing machine M, there is an A such that P^A = NP^A and either M^A does not compute SAT correctly on all inputs or M^A takes at least exponential time.

Proof:

Define B = {0x | x in TQBF}. TQBF is the PSPACE-complete problem containing all the true quantified Boolean formula. P^TQBF = PSPACE = NP^TQBF and thus P^B = NP^B.

Let φ_n be the formula that is true if there exists a string z of length n such that 1z is in A. Let n be the smallest n such that M^B(φ_n) takes less than 2ⁿ computational steps. If no such n exists let A = B and we are done.

If M^B(φ_n) accepts again we are done by letting A=B since B has no string beginning with 1.

If M^B(φ_n) rejects and uses less than 2ⁿ steps there must be some z such that M^B(φ_n) did not query 1z. Let A = B ∪ {1z}.

M^A(φ_n) still rejects but now φ_n is in SAT^A. Also P^A = NP^A since adding a single string to an oracle won't affect whether two classes collapse.
Computational Complexity published first on Computational Complexity