3 ms·
I'm 90% sure the first paper proving P!=NP will either use a Kolmogorov complexity argument, or an exact enumeration involving a semigroup problem that is expon
by crb002 9y ago
I'm 90% sure the first paper proving P!=NP will either use a Kolmogorov complexity argument, or an exact enumeration involving a semigroup problem that is exponential.
- Ar-Curunir 9y agoAny clarification on how you expect such arguments to be used? Otherwise your claims are completely out of left field, because most approaches are not anything along those lines.
- sn41 9y agoKolmogorov had an outline of an attempt using Kolmogorov Complexity to settle P vs NP. I do not unfortunately recall the crux of the argument. This was formulated in the 1970s, and has not been followed up as far as I know. On the other hand, given Baker-Gill-Solovay and the Natural Proof barriers, no proof settling the question is expected to be easy.