Tetris é NP-hard!

Encontrei esta folheando o Universal Book of Mathematics, de David Darling: o jogo de Tetris é um problema tipo NP  NP-hard! Lá se vai minha estratégia de manter o número de linhas o mais baixo possível…
Explicando: NP NP-hard é uma classe de complexidade que reúne problemas que não têm uma fórmula geral de solução. Por exemplo, uma conta de multiplicar não é NP NP-hard, porque existe um procedimento, o algoritmo da multiplicação, que se for aplicado corretamente gera o produto de dois números, não importa que números sejam esses. 
Já para encontrar a saída de um labirinto não existe nenhum algoritmo onde, digamos, informando-se o comprimento médio dos corredores e o número esquinas à direita, obtém-se uma rota de saída. O único jeito de resolver um problema NP  NP-hard é testar todas as soluções plausíveis, até que uma delas funcione. O consolo é que é fácil testar os candidatos — o procedimento de teste é, como se diz, computável.
O fato de Tetris ser NP NP-hard significa que nenhuma estratégia — como a minha favorita, de eliminar toda linha que possa ser eliminada o quanto antes — garante pontuação máxima. O único jeito de descobrir qual a melhor estratégia para pontuar numa partida é jogando a partida; com o corolário de que, quando a estratégia tiver sido descoberta a partida terá acabado, o que torna a estratégia inútil, porque ela provavelemente não vai funcionar na próxima partida.
Até soa como algo profundo, acho.

Discussão - 4 comentários

  1. glommer disse:

    De onde você tirou essa definição da classe NP? NP contém todos os problemas em P, (P está contido em NP), e para todos os problemas P, é possivel achar algoritmos com uma "fórmula geral" de solução.

  2. cretinas disse:

    É verdade... Eu devia ter sido mais claro e definido a categoria direito, como NP-difícil (NP-hard).

  3. cretinas disse:

    E, claro, explicitado a presunção de que P é diferente de NP-completo(essas emendas estão ficando piores que o soneto...).
    Expandindo: NP é a classe dos problemas onde, tendo-se uma possível solução, é fácil testá-la; dentro dela está a classe dos problemas P, onde, além de ser fácil testar uma possível solução, também é fácil descobrior uma solução por nmeio de um algoritmo.
    Já a situação dos problemas NP ainda é duvidosa. A questão de se os problemas NP-completos (que podem ser testados e, portanto resolvidos por um método de exaustão) podem ser reduzidos à subcategoria de problemas P (resolvíveis por algoritmos rápidos, e também por exaustão) ainda está aberta, mas a maioria das apostas indica que P é diferente de NP.

Envie seu comentário

Seu e-mail não será divulgado. (*) Campos obrigatórios.

Categorias

Sobre ScienceBlogs Brasil | Anuncie com ScienceBlogs Brasil | Política de Privacidade | Termos e Condições | Contato


ScienceBlogs por Seed Media Group. Group. ©2006-2011 Seed Media Group LLC. Todos direitos garantidos.


Páginas da Seed Media Group Seed Media Group | ScienceBlogs | SEEDMAGAZINE.COM