{"id":244,"date":"2008-10-27T08:51:55","date_gmt":"2008-10-27T11:51:55","guid":{"rendered":"http:\/\/scienceblogs.com.br\/cretinas\/2008\/10\/tetris-e-np\/"},"modified":"2008-10-27T08:51:55","modified_gmt":"2008-10-27T11:51:55","slug":"tetris-e-np","status":"publish","type":"post","link":"https:\/\/www.blogs.unicamp.br\/cretinas\/2008\/10\/27\/tetris-e-np\/","title":{"rendered":"Tetris \u00e9 NP-hard!"},"content":{"rendered":"<p>Encontrei esta folheando o <em>Universal Book of Mathematics<\/em>, de David Darling: o jogo de <a href=\"http:\/\/www.freetetris.org\/\" target=\"_blank\" rel=\"noopener noreferrer\">Tetris<\/a> \u00e9 um problema tipo <span style=\"text-decoration: line-through\">NP\u00a0 <\/span>NP-hard! L\u00e1 se vai minha estrat\u00e9gia de manter o n\u00famero de linhas o mais baixo poss\u00edvel&#8230;<br \/>\nExplicando: <span style=\"text-decoration: line-through\">NP<\/span> NP-hard \u00e9 uma classe de complexidade que re\u00fane problemas que n\u00e3o t\u00eam uma f\u00f3rmula geral de solu\u00e7\u00e3o. Por exemplo, uma conta de multiplicar n\u00e3o \u00e9 <span style=\"text-decoration: line-through\">NP<\/span> NP-hard, porque existe um procedimento, o algoritmo da multiplica\u00e7\u00e3o, que se for aplicado corretamente gera o produto de dois n\u00fameros, n\u00e3o importa que n\u00fameros sejam esses.\u00a0<br \/>\nJ\u00e1 para encontrar a sa\u00edda de um labirinto n\u00e3o existe nenhum algoritmo onde, digamos, informando-se o comprimento m\u00e9dio dos corredores e o n\u00famero esquinas \u00e0 direita,\u00a0obt\u00e9m-se uma rota de sa\u00edda. O \u00fanico jeito de resolver um problema <span style=\"text-decoration: line-through\">NP<\/span>\u00a0 NP-hard \u00e9 <em>testar todas as solu\u00e7\u00f5es plaus\u00edveis<\/em>, at\u00e9 que uma delas funcione. O consolo \u00e9 que \u00e9 f\u00e1cil testar os candidatos &#8212; o procedimento de teste \u00e9, como se diz, comput\u00e1vel.<br \/>\nO fato de Tetris ser <span style=\"text-decoration: line-through\">NP<\/span> NP-hard significa que nenhuma estrat\u00e9gia &#8212; como a minha favorita, de eliminar toda linha que possa ser eliminada o quanto antes &#8212; garante pontua\u00e7\u00e3o m\u00e1xima. O \u00fanico jeito de descobrir qual a melhor estrat\u00e9gia para pontuar numa partida \u00e9 jogando a partida; com o corol\u00e1rio de que, quando a estrat\u00e9gia tiver sido descoberta a partida ter\u00e1 acabado, o que torna a estrat\u00e9gia in\u00fatil, porque ela provavelemente n\u00e3o vai funcionar na <em>pr\u00f3xima<\/em> partida.<br \/>\nAt\u00e9 soa como algo profundo, acho.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Encontrei esta folheando o Universal Book of Mathematics, de David Darling: o jogo de Tetris \u00e9 um problema tipo NP\u00a0 NP-hard! L\u00e1 se vai minha estrat\u00e9gia de manter o n\u00famero de linhas o mais baixo poss\u00edvel&#8230; Explicando: NP NP-hard \u00e9 uma classe de complexidade que re\u00fane problemas que n\u00e3o t\u00eam uma f\u00f3rmula geral de solu\u00e7\u00e3o. [&hellip;]<\/p>\n","protected":false},"author":545,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"pgc_sgb_lightbox_settings":"","_vp_format_video_url":"","_vp_image_focal_point":[],"footnotes":""},"categories":[3],"tags":[],"class_list":["post-244","post","type-post","status-publish","format-standard","hentry","category-geral"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts\/244","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/users\/545"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/comments?post=244"}],"version-history":[{"count":0,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts\/244\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/media?parent=244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/categories?post=244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/tags?post=244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}