A Solution of the P versus NP Problem

Revision en1, by limed, 2017-08-16 22:00:38

Thought this would be interesting to many: https://arxiv.org/abs/1708.03486

Norbert Blum

(Submitted on 11 Aug 2017)

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English limed 2017-08-16 22:00:38 516 Initial revision (published)