{"id":58,"date":"2011-01-20T21:45:27","date_gmt":"2011-01-20T20:45:27","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=58"},"modified":"2011-01-22T02:19:13","modified_gmt":"2011-01-22T01:19:13","slug":"3-sat-polynomial-time-solution-if-true-then-pnp","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/01\/20\/3-sat-polynomial-time-solution-if-true-then-pnp\/","title":{"rendered":"3-SAT polynomial time solution? If true then P==NP"},"content":{"rendered":"<div style=\"width: 262px\" class=\"wp-caption alignleft\"><img loading=\"lazy\" class=\"  \" title=\"Complexity classes\" src=\"http:\/\/upload.wikimedia.org\/wikipedia\/commons\/4\/4a\/Complexity_classes.png\" alt=\"Complexity classes\" width=\"252\" height=\"156\" \/><p class=\"wp-caption-text\">Complexity classes<\/p><\/div>\n<p>One of the biggest questions in the <acronym title=\"Computer Science\">CS<\/acronym> always was (is) if <a href=\"https:\/\/secure.wikimedia.org\/wikipedia\/en\/wiki\/P_(complexity)\" target=\"_new\">P<\/a>==<a href=\"https:\/\/secure.wikimedia.org\/wikipedia\/en\/wiki\/NP_(complexity)\" target=\"_new\">NP<\/a>, or P!=NP.<\/p>\n<p>I just read a <a href=\"http:\/\/romvf.wordpress.com\/2011\/01\/19\/open-letter\/\" target=\"_new\">post<\/a> announcing an article called <em>\u201cNon-Orthodox Combinatorial Models Based on Discordant Structures\u201d<\/em> by the author V. F. Romanov (<a href=\"http:\/\/arxiv.org\/abs\/1011.3944\" target=\"_blank\">http:\/\/arxiv.org\/abs\/1011.3944<\/a>).<\/p>\n<p>According to the author:<\/p>\n<blockquote><p>The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied by description of a polynomial algorithm created for the named purpose.<\/p><\/blockquote>\n<p>If this statement is correct, and the algorithm really solves the <a href=\"https:\/\/secure.wikimedia.org\/wikipedia\/en\/wiki\/3-SAT#3-satisfiability\" target=\"_blank\">3-SAT<\/a> problem in polynomial time, then P==NP (since 3-SAT is \u00a0<a href=\"https:\/\/secure.wikimedia.org\/wikipedia\/en\/wiki\/NP-complete\" target=\"_blank\">NP-complete<\/a>). Although the article, in my opinion, looks too draft for such an important topic, <strong>if it will be proven correct, one of the biggest findings in CS will be unveiled.<\/strong><\/p>\n<p>Lets see..<\/p>\n","protected":false},"excerpt":{"rendered":"<p>One of the biggest questions in the CS always was (is) if P==NP, or P!=NP. I just read a post announcing an article called \u201cNon-Orthodox Combinatorial Models Based on Discordant Structures\u201d by the author V. F. Romanov (http:\/\/arxiv.org\/abs\/1011.3944). According to the author: The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[14],"tags":[15,16,13],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1ouW6-W","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/58"}],"collection":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/comments?post=58"}],"version-history":[{"count":16,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/58\/revisions"}],"predecessor-version":[{"id":74,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/58\/revisions\/74"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=58"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=58"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=58"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}