3 ms·
The paper looks like it is 38 pages and builds on other work. That doesn't seem too simple to me.
by btilly 9y ago
The paper looks like it is 38 pages and builds on other work. That doesn't seem too simple to me.
- ethan_g 9y agoI 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.
- daveFNbuck 9y agoThe 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.