The discussion centers on Norbert Blum's 2017 paper claiming P ≠ NP, which utilizes CNF-DNF-approximators to establish exponential lower bounds for the monotone network complexity of specific functions. Experts express skepticism about the validity of the proof, with references to potential flaws highlighted in subsequent discussions. The consensus leans towards the belief that the proof may not withstand scrutiny, as indicated by ongoing debates in the theoretical computer science community.
PREREQUISITESThe discussion is beneficial for theoretical computer scientists, mathematicians specializing in complexity theory, and researchers interested in the P vs NP problem and its implications in computational theory.
andBerg and Ulfberg and Amano and Maruoka .. have used ... to prove exponential lower bound ...
This is the way science works: A great result from one author(s), because non-trivial lower bounds are really hard to prove, and another one generalizes the result. And as with Poincaré, the result ##P \neq NP## is simply a corollary.We [Blum] show that these approximators can be used to prove the same lower bound for ...
fresh_42 said:If it is true, then it will be a sensation and I wonder, why the usual pop-science shout-boxes haven't reacted yet.
Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.
gravenewworld said:What can the experts decipher on this:
https://arxiv.org/pdf/1708.03486.pdf
Is this going to win a million dollars?
EDIT: The punchline is P =/= NP
The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage