Até computadores acham Super Mario Bros. difícil

14

Receba atualizações em tempo real diretamente no seu dispositivo, inscreva-se agora.

Se você já se esforçou para passar de nível em Super Mario Bros., uma pesquisa do Massachusetts Institute of Technology (MIT) vai deixar você mais feliz. O mundo de Mario é matematicamente difícil.

De acordo com um novo estudo, o jogo pode ser tão difícil quanto os mais difíceis problemas de PSPACE.

PSPACE é uma classe de complexidade em ciência da computação que agrupa os problemas conforme seus graus de dificuldade. PSPACE é o conjunto de todos os problemas que levam uma quantidade “polinomial” de espaço de memória para ser resolvido.

Um algoritmo que precisa resolver através de N números para encontrar o maior, por exemplo, precisaria de um espaço de memória proporcional à N. Se quisermos ter uma lista da distância entre as cidades de N país, precisaríamos de um espaço N², porque para cada cidade o algoritmo teria que calcular a distância até todas as outras.

Alguns problemas em PSPACE podem ser fáceis de resolver, enquanto outros podem ser difíceis, mas a solução pode ser fácil de se verificar. Os problemas mais difíceis são difíceis de se resolver e também difíceis de se verificar. Você pode criar um nível de Super Mario que um algoritmo levaria um tempo tão longo para resolver quanto para chegar até a resposta mesmo tendo a resolução.

“Estou realmente animado com esse tipo de comprovação de dificuldade”, disse Erik Demaine, coautor do artigo. “Isso acumula muita experiência para tornar a resolução de problemas mais fácil. Quanto mais prática nós temos, melhores somos em resolver esse tipo de problema. Além disso, é importante saber as limitações dos algoritmos.” [IFFCG]

 

Receba atualizações em tempo real diretamente no seu dispositivo, inscreva-se agora.

Comentários
Carregando...