3 ms·
The author claims to have a proof that NP = coNP = PSPACE along the following lines: first they describe their favorite axiomatic logical system, then they clai
by cevi 5y ago
The author claims to have a proof that NP = coNP = PSPACE along the following lines: first they describe their favorite axiomatic logical system, then they claim to have a method to compress quasipolynomial-sized proofs in this system to polynomial-sized proofs. If their claimed proof worked, it would be a breakthrough the likes of which math has never seen before - NP = coNP means that every easily stated puzzle with no solution has a short proof of unsolvability (NP = coNP is widely believed to be false).
Looking at some of the previous papers (such as [1]) building towards the proof (which appear to have actually been published?!), I don't see any magic. It looks complex enough that the author probably fooled themself, but there doesn't seem to be any amazing new algorithmic ingredient such as the idea behind the fast fourier transform or fast matrix multiplication. Color me extremely skeptical.
[1] https://arxiv.org/pdf/1907.03858.pdf https://arxiv.org/pdf/1907.03858.pdf