{"id":1816,"date":"2012-01-27T06:56:25","date_gmt":"2012-01-27T06:56:25","guid":{"rendered":"http:\/\/paslongtemps.net\/blog\/2012\/01\/27\/pac-man-np-hard-boulder-dash-first-star\/"},"modified":"2020-04-05T17:42:46","modified_gmt":"2020-04-05T15:42:46","slug":"pac-man-np-hard-boulder-dash-first-star","status":"publish","type":"post","link":"https:\/\/paslongtemps.net\/blog\/2012\/01\/27\/pac-man-np-hard-boulder-dash-first-star\/","title":{"rendered":""},"content":{"rendered":"\n\t\t<style type=\"text\/css\">\n\t\t\t#gallery-1 {\n\t\t\t\tmargin: auto;\n\t\t\t}\n\t\t\t#gallery-1 .gallery-item {\n\t\t\t\tfloat: left;\n\t\t\t\tmargin-top: 10px;\n\t\t\t\ttext-align: center;\n\t\t\t\twidth: 33%;\n\t\t\t}\n\t\t\t#gallery-1 img {\n\t\t\t\tborder: 2px solid #cfcfcf;\n\t\t\t}\n\t\t\t#gallery-1 .gallery-caption {\n\t\t\t\tmargin-left: 0;\n\t\t\t}\n\t\t\t\/* see gallery_shortcode() in wp-includes\/media.php *\/\n\t\t<\/style>\n\t\t<div id='gallery-1' class='gallery galleryid-1816 gallery-columns-3 gallery-size-thumbnail'><dl class='gallery-item'>\n\t\t\t<dt class='gallery-icon portrait'>\n\t\t\t\t<a href='https:\/\/paslongtemps.net\/blog\/2012\/01\/27\/pac-man-np-hard-boulder-dash-first-star\/attachment\/1817\/'><img loading=\"lazy\" decoding=\"async\" width=\"150\" height=\"150\" src=\"https:\/\/paslongtemps.net\/blog\/wp-content\/uploads\/sites\/3\/2012\/01\/tumblr_lyg3a2ZqO81qz9b1ho1_250-150x150.png\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" \/><\/a>\n\t\t\t<\/dt><\/dl>\n\t\t\t<br style='clear: both' \/>\n\t\t<\/div>\n\n<p>Pac-Man : NP-Hard<br \/>Boulder Dash (First Star Software, 1984) is NP-hard. Deflektor (Vortex Software, 1987) is in L.<br \/>Prince of Persia (Br\u00f8derbund, 1989) is PSPACE-complete.<br \/>Tron (Bally Midway, 1982) is NP-hard.<\/p>\n<p>(via <a href=\"http:\/\/www.technologyreview.com\/blog\/arxiv\/27528\/?p1=A2\">Pac-Man Proved NP-Hard By Computational Complexity Theory &#8211; Technology Review<\/a>)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pac-Man : NP-HardBoulder Dash (First Star Software, 1984) is NP-hard. Deflektor (Vortex Software, 1987) is in L.Prince of Persia (Br\u00f8derbund, 1989) is PSPACE-complete.Tron (Bally Midway, 1982) is NP-hard. (via Pac-Man Proved NP-Hard By Computational Complexity Theory &#8211; Technology Review)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"gallery","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1816","post","type-post","status-publish","format-gallery","hentry","category-uncategorized","post_format-post-format-gallery"],"_links":{"self":[{"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/posts\/1816","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/comments?post=1816"}],"version-history":[{"count":1,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/posts\/1816\/revisions"}],"predecessor-version":[{"id":1818,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/posts\/1816\/revisions\/1818"}],"wp:attachment":[{"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/media?parent=1816"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/categories?post=1816"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/paslongtemps.net\/blog\/wp-json\/wp\/v2\/tags?post=1816"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}