The problem (or, according to some posters, one of the problems) with your idea is that the concept of a polynomial-time algorithm is itself a mathematical question and not a question about reality. If I gave you the running times of an algorithm for input sizes from 1 to 3^^^3, this would not tell you whether the algorithm is polynomial. However, it would answer the question as far as reality is concerned, since it’s impossible to perform the algorithm on inputs bigger than that (or even remotely close to that size).
For simple algorithms like bubble sort or whatnot, we can look at the algorithm and say, “oh, that’s quadratic time” and that lets us make predictions about how long it will take to run (if it takes 10 seconds to sort a 10^9 element array, then it will probably take 1000 seconds to sort a 10^10 element array). But this is not a statement about reality directly—this is a mathematical statement which describes reality, in this case.
Furthermore, it is impossible to make this sort of statement in general. Just as we can’t tell if an arbitrary program halts or not, we cannot in general say if an arbitrary algorithm runs in polynomial time. In fact, I’d bet that one can construct an algorithm such that the question whether the algorithm runs in polynomial time is independent of ZFC. This is not a question of ZFC failing to describe reality, because it’s not a question about reality whether the algorithm is polynomial, to begin with.
As for P=NP… there’s actually an interesting exercise that I’d expect anyone in a good theoretical CS class to see. Right now, without doing cutting-edge research, I can write down an algorithm for solving 3SAT with the following property: if P=NP, then the algorithm I write down will run in polynomial time (and obviously the converse also holds). Thus, deciding whether P=NP is isomorphic to determining the running time of this algorithm (which has a very simple description!) As I’ve stated earlier, it would not be too surprising if this question turned out to be independent of ZFC.
Edit: it appears that my last paragraph has been preempted.
The problem (or, according to some posters, one of the problems) with your idea is that the concept of a polynomial-time algorithm is itself a mathematical question and not a question about reality. If I gave you the running times of an algorithm for input sizes from 1 to 3^^^3, this would not tell you whether the algorithm is polynomial. However, it would answer the question as far as reality is concerned, since it’s impossible to perform the algorithm on inputs bigger than that (or even remotely close to that size).
For simple algorithms like bubble sort or whatnot, we can look at the algorithm and say, “oh, that’s quadratic time” and that lets us make predictions about how long it will take to run (if it takes 10 seconds to sort a 10^9 element array, then it will probably take 1000 seconds to sort a 10^10 element array). But this is not a statement about reality directly—this is a mathematical statement which describes reality, in this case.
Furthermore, it is impossible to make this sort of statement in general. Just as we can’t tell if an arbitrary program halts or not, we cannot in general say if an arbitrary algorithm runs in polynomial time. In fact, I’d bet that one can construct an algorithm such that the question whether the algorithm runs in polynomial time is independent of ZFC. This is not a question of ZFC failing to describe reality, because it’s not a question about reality whether the algorithm is polynomial, to begin with.
As for P=NP… there’s actually an interesting exercise that I’d expect anyone in a good theoretical CS class to see. Right now, without doing cutting-edge research, I can write down an algorithm for solving 3SAT with the following property: if P=NP, then the algorithm I write down will run in polynomial time (and obviously the converse also holds). Thus, deciding whether P=NP is isomorphic to determining the running time of this algorithm (which has a very simple description!) As I’ve stated earlier, it would not be too surprising if this question turned out to be independent of ZFC.
Edit: it appears that my last paragraph has been preempted.
Also: upvoted for an interesting question.