14 Aug
2017
14 Aug
'17
4:23 p.m.
Whoa. Anyone have opinions on this? https://arxiv.org/pdf/1708.03486.pdf "A Solution of the P versus NP Problem" Norbert Blum Institut f¨ur Informatik, Universit¨at Bonn Friedrich-Ebert-Allee 144, D-53113 Bonn, Germany email: blum@cs.uni-bonn.de August 14, 2017 *Abstract* Berg and Ulfberg [4] and Amano and Maruoka [2] have used CNFDNF-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 != NP. --Michael -- Forewarned is worth an octopus in the bush.