{"id":174,"date":"2012-10-02T20:33:13","date_gmt":"2020-02-18T06:53:26","guid":{"rendered":"https:\/\/redfrontdoor.org\/blg2\/?p=174"},"modified":"2020-02-18T16:51:43","modified_gmt":"2020-02-18T16:51:43","slug":"post-168","status":"publish","type":"post","link":"https:\/\/redfrontdoor.org\/blog\/?p=174","title":{"rendered":"MazezaM is NP complete"},"content":{"rendered":"<p style=\"background-color:#ffc;padding: 6px\">Update 20170129: My claim that Mazezam is NP-complete is <strong>not<\/strong> shown by this argument.  The argument does show that Mazezam is NP-hard, but it is not clear that Mazezam is itself in NP.  See <a href=\"\/blog\/?p=1336\">a follow-up post<\/a> for more details.  Many thanks to <a href=\"https:\/\/simons-rock.edu\/academics\/faculty-bios\/science-mathematics-and-computing-faculty\/aaron-williams.php\">Aaron Williams<\/a> for contacting me to point out my error.<\/p>\n<div style=\"float:right;margin-left:1em\"><img decoding=\"async\" src=\"\/blog\/wp-content\/uploads\/2012\/10\/mazezam-screenshot-sml.png\"><\/div>\n<p>The <a href=\"\/blog\/?p=111\">post about AutoFickle<\/a> reminded me of something I did a good while ago (2008) which doesn&#8217;t currently have a home.  The connection is that this is also a project based on a game written by Malcolm Tyrrell.  The game this time is <a href=\"https:\/\/sites.google.com\/site\/malcolmsprojects\/mazezam-home-page\" title=\"Malcolm Tyrrell: MazezaM\">MazezaM<\/a>, dated 2002&ndash;2004; in it you push rows of blocks back and forth, trying to get from the entrance to the exit of a maze.  It&#8217;s a nice game.<\/p>\n<p>It seemed like the sort of thing which ought to be NP-complete, in the same way that other puzzle games have turned out to be.  (See, e.g., <a href=\"http:\/\/www.ics.uci.edu\/~eppstein\/cgt\/hard.html\" title=\"David Eppstein: Computational Complexity of Games and Puzzles\">David Eppstein&#8217;s page &#8216;Computational Complexity of Games and Puzzles&#8217;<\/a> for a thorough survey.)  I think I managed to demonstrate that MazezaM is, indeed, NP-complete.<\/p>\n<p>The argument is sketched in <a href=\"\/blog\/wp-content\/uploads\/2012\/10\/MazezaM-NP-complete.pdf\" title=\"Mazezam is NP complete\">this PDF<\/a>.  The conclusion is that you can construct a MazezaM level like<\/p>\n<p style=\"text-align:center\"><img decoding=\"async\" src=\"\/blog\/wp-content\/uploads\/2012\/10\/map-3SAT-equiv.png\"><\/p>\n<p>to represent an instance of the Boolean satisfiability problem (3-SAT), where solving the MazezaM level is equivalent to finding an assignment of the variables in the 3-SAT instance.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update 20170129: My claim that Mazezam is NP-complete is not shown by this argument. The argument does show that Mazezam is NP-hard, but it is not clear that Mazezam is itself in NP. See a follow-up post for more details. Many thanks to Aaron Williams for contacting me to point out my error. The post about AutoFickle reminded me of something I did a good while ago (2008) which doesn&#8217;t currently have a home. The connection is that this is also a project based on a game written by Malcolm Tyrrell. The game this time is MazezaM, dated 2002&ndash;2004; in it you push rows of blocks back and forth, trying to get from the entrance to the exit of a<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-174","post","type-post","status-publish","format-standard","hentry","category-uncategorized","comments-off"],"_links":{"self":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/174","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=174"}],"version-history":[{"count":1,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/174\/revisions"}],"predecessor-version":[{"id":2172,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/174\/revisions\/2172"}],"wp:attachment":[{"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=174"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/redfrontdoor.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}