Além de NP: Um Problema de Complexidade Mais Intuitivo
2025-04-17
O autor questiona o uso do Problema da Parada como o exemplo canônico de um problema mais difícil que NP-completo, argumentando que é confuso e pouco intuitivo. Embora indecidível, a verificação de uma resposta "sim" para o Problema da Parada pode ser feita executando o programa por um número finito de etapas. Uma alternativa mais fácil de entender é apresentada: mover uma peça em uma grade infinita para atingir um ponto alvo. Este problema é PSPACE-completo em dimensões inferiores, mas sua complexidade explode com o aumento das dimensões, eventualmente atingindo a completude de ACKERMANN, demonstrando visualmente uma complexidade muito além dos problemas NP.