Is there any evidence that P might be equal to NP? This seems different from other famous conjectures like Fermat's Last Theorem or Riemann's Theorem where what's hard is finding a counterexample that disproves the theory.
Note that Knuth does not believe that the constant factor on the P algorithm be will be less than the size of the entire Universe.
I've heard of those, even tried to read the proof. Still, my understanding is those claims are ultimately "informal proofs" despite having formal step so the situation isn't entirely closed-up but still very bad.
A strict subset B
they also show
A^O strict subset B^O
for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem)
However, we know (Baker, Gill, Solovay) that there exists and oracle O1 where
P^O1 subset NP^O1
as well as an oracle O2 such that
P^O2 not subset NP^O2
Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.
P^O1 strict subset NP^O1
and
P^O2 equals NP^O2
B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization")
C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind of unnatural). Search up "time hierarchy theorem". This is probably one of the theorems you mention. However, you're right, as far as natural problems go, it appears to be extreme difficult to prove most natural problems takes at least linear time (https://mathoverflow.net/questions/4953/super-linear-time-co...). Note the log*... factor grows extremely slowly.
In fact, it is not known whether SAT requires more than linear time. Since SAT is NP-complete, we expect it to have no polynomial time algorithm... and yet here we are wondering whether it requires even more than linear time. If you are interested in this sort of thing, maybe look up fine-grained complexity. Also note that to solve P != NP, we will have to atleast shown P != PSPACE, since PSPACE contains NP. However, even this seemingly easier problem has had no progress and seems like it would require a huge breakthrough.