{"id":71948,"date":"2017-08-15T22:48:46","date_gmt":"2017-08-16T05:48:46","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2017\/08\/a-solution-of-the-p-versus-np-problem"},"modified":"2017-08-15T22:55:47","modified_gmt":"2017-08-16T05:55:47","slug":"a-solution-of-the-p-versus-np-problem","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2017\/08\/a-solution-of-the-p-versus-np-problem","title":{"rendered":"A Solution of the P versus NP Problem"},"content":{"rendered":"<p>Abstract: 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\u2019s 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.<\/p>\n<p><!-- Link: <a href=\"https:\/\/arxiv.org\/abs\/1708.03486\">https:\/\/arxiv.org\/abs\/1708.03486<\/a> --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Abstract: 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\u2019s 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.<\/p>\n","protected":false},"author":368,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523],"tags":[],"class_list":["post-71948","post","type-post","status-publish","format-standard","hentry","category-computing"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/71948","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/368"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=71948"}],"version-history":[{"count":1,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/71948\/revisions"}],"predecessor-version":[{"id":71949,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/71948\/revisions\/71949"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=71948"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=71948"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=71948"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}