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."

## No comments:

## Post a Comment