On Norbert Blum’s claimed proof that P does not equal NP

Re:On Norbert Blum’s claimed proof that P does not equal NP by crb002 on Wednesday August 16, 2017 @01:24PM (#15029325)

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.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by Ar-Curunir on Wednesday August 16, 2017 @04:54PM (#15031295)

Any 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.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by sn41 on Thursday August 17, 2017 @12:34AM (#15033834)

Kolmogorov 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.

[ Parent | on HN ]