blog.computationalcomplexity.org · 18h · discuss
(Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.)I wrote the following about 2 years ago but did not post it. It's dated, but that's the point.BEGIN DOCUMENT FROM TWO YEARS AGOWhy do we think \(P\ne NP\)?a) Lots of people have worked on SAT and other NP-complete problems, without getting them in P. This is not mathematical evidence but it is worth noting.b) If SAT is in P then all problems in NP are in P. This implication is one reason I think \(P\ne NP\) is true. I...