Hacker News new | ask | show | jobs
by ethan_g 3231 days ago
I tend to agree with GP that this is suspiciously simple. I've only skimmed it, but the novel part of the proof appears to only be Thm 5-6 which is less than 10 pages, and it's not especially dense writing. So this would be a relatively simple proof. Moreover, the technique used appears to be rather incremental over known techniques, so it's surprising it would be strong enough to prove PvNP which is so far away from the frontier of known techniques.
1 comments

The known technique was a proof of an exponential lower bound on something extremely similar to an NP-complete problem. That moved the frontier of known techniques a lot closer to P vs NP.