Hmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
Yes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant.
Of course, that constant is astronomically unpractical.
I like the term "Galactic Algorithm" for these algorithms with unpractical constants.
https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
It involves iterating through and running all possible programs ordered by length, giving them an increasing amount of time to run and checking (in polynomial time) if they produce the correct answer.
If there exists a program that finds the answer in polynomial time, this algorithm will eventually find it after wasting (at most polynomial) time iterating through other programs and tentative bounds.
If P != NP, it's still at least asymptotically optimal.