The Buzz

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima. They claim to show that no polynomial-time machine can produce a proof of a super-polynomial-time lower bound for NP and as a consequence there is no proof that P≠NP in any reasonable proof system such as Peano Arithmetic. The first part I don't really understand but the latter would be a major breakthrough.

But don't get too excited. I have heard from multiple sources that Razborov has found serious problems in their paper, in particular that Theorem 22 is just false. So as one complexity theorist put it, "This is probably not the most important paper on your stack."