Se a viagem no tempo é possível, então P=NP?

Eu fiquei sabendo “há pouco tempo” de uma simulação de viagem no tempo no nível quântico (ps: as aspas no começo da frase foi uma semi-piada sem graça), uma tentativa de ampliar o entendimento que ajude na criação de uma (tão almejada) teoria de unificação da relatividade geral com mecânica quântica, vislumbrando a solução para paradoxos ligados a causalidade (como o paradoxo do avô).

Paradoxo no desenho de Escher
Paradoxo de causalidade no desenho de Escher

O experimento foi realizado no ano passado (2014) na Universidade de Queensland (Austrália) pela equipe do professor Tim Ralph. Mas não me pergunte detalhes sobre isso, eu estou longe de ser a pessoa mais adequada para explicar… Parece que eles conseguiram simular o envio de um fóton para o passado, fóton este responsável por ativar a sua própria fonte. Ou seja, o fóton é a causa passada dele mesmo: o “ovo” e também a “galinha”, sendo esta mesma “galinha” a que “pôs o seu ovo”. Mundo estranho esse que a gente vive sem se dar conta de sua estranheza.

Causalidade e viagem no tempo
Causalidade e viagem no tempo

O fato é que a simulação me fez lembrar de uma reflexão (não documentada) que fiz no final de 2013 sobre as implicações da possibilidade de viagem no tempo em complexidade de algoritmos, em especial no principal problema em aberto na teoria da computação: P=NP?

Penso que o raciocínio subjacente é tão simples que me dá a impressão de que esta reflexão já foi feita por alguém. Provavelmente por algum físico que conheça alguma coisa sobre os limites da Computação. Me surpreende um pouco o fato de eu nunca ter ouvido falar em algo similar na universidade.

Caro leitor, se sua formação é em Computação fique à vontade para pular as próximas três seções. Não vou entrar em nenhum formalismo aqui, mas se você está meio esquecido dos fundamentos vale a pena relembrar.

Computabilidade

O objeto da Computação é a resolução de problemas. Em geral, a resolução mais geral de um problema envolve a definição de uma relação matemática, ou seja, o mapeamento de uma entrada (pertencente a um conjunto de entradas) em uma saída (pertencente a um conjunto de saídas). Como uma relação é abstrata demais para fins de engenharia, a Ciência da Computação define um objeto matemático que traduz uma relação em uma sequência de procedimentos que transformam entradas em saídas, o algoritmo.

Para você entender melhor, imagine que seu problema seja fazer um bolo. Existe então uma relação que mapeia ingredientes (de um conjunto de possíveis ingredientes) em seu bolo (de um conjunto de possíveis bolos). Oquei.  Mas se você quer mesmo fazer um bolo, deve entender que apenas conhecer quais ingredientes estão mapeados para quais tipos de bolos não ajuda muito… é preciso conhecer o algoritmo do bolo. Veja aqui um exemplo de tal algoritmo (seção “Modo de preparo”).

Alan Turing
Alan Turing

Em tecnologia da informação existem problemas bem mais complicados que fazer bolo. Os problemas são tão variados que, para fins práticos, precisamos de um computador de propósito geral, uma máquina programável que possui um conjunto de instruções que, quando combinadas coerente e diferentemente, produzem uma infinidade de algoritmos. As arquiteturas de computadores atuais são implementações da máquina de Turing, um modelo de computação teórico da década de 1930 criado por Alan Turing. Aliás, se quiser conhecer um pouco sobre esse cara existe um bom filme sobre ele chamado The Imitation Game, que chegou nos cinemas do Brasil agora em janeiro de 2015. Do ponto de vista histórico é meio fantasioso em alguns aspectos mas vale a pena assistir.

Filme "The Imitation Game"
Filme “The Imitation Game”

Em teoria da computabilidade, dizemos que um problema é computável se existe uma máquina de Turing que o resolva, ou equivalentemente, se existe um algoritmo para ele. Existem vários tipos propostos de máquinas de Turing, todos equivalentes em expressividade. No que diz respeito ao não-determinismo, as máquinas de Turing podem ser classificadas em determinísticas e não-determinísticas.

Máquinas de Turing determinísticas e não-determinísticas

Exemplo de máquina de Turing
Exemplo de máquina de Turing

Uma máquina de Turing determinística consegue realizar computação para resolver um problema através de passos que são escolhidos de forma não-ambígua, significando que para cada símbolo processado em um dado estado da computação existe apenas um estado futuro possível. Já uma máquina de Turing não-determinística é ambígua, no sentido de que existe pelo menos uma situação na computação em que a máquina tem que decidir para qual estado migrar. Neste caso, diz-se que a máquina sempre “sabe” para qual estado migrar, aquele que aceita a computação, ou o que realiza a computação com sucesso. Uma máquina de Turing não-determinística pode ser facilmente simulada em uma máquina de Turing determinística. Basicamente, basta fazer com que a máquina de Turing determinística execute todas as possibilidades geradas pela ambiguidade da máquina de Turing não-determinística.

Por exemplo, considere o problema de satisfação de restrições descrito neste link (curiosidade: lá está descrito como um teste de QI inventado por Einstein, mas não sei se é verdade que foi inventado por ele… mas com certeza não é um teste de QI, pois não há como extrair dele um quociente que indique a idade intelectual do avaliado). Uma máquina de Turing não-determinística para resolver este problema é trivial… ela deve produzir em um passo justamente aquele conjunto de parâmetros que satisfazem as restrições impostas, resolvendo “misteriosamente” a ambiguidade na escolha das transições levam à resposta correta. Uma máquina de Turing determinística, por outro lado, deve testar todas as combinações possíveis de parâmetros até encontrar aquela que satisfaz as restrições. Embora as duas sejam equivalentes em teoria, apenas a última é implementável atualmente. Mas como nada é de graça, também possui a implementação mais custosa.

Complexidade e classes de complexidade de problemas

Algoritmo Heapsort (ordenação), que possui complexidade da ordem de N*log(N)
Algoritmo Heapsort (ordenação), que possui complexidade da ordem de N*log(N)

Assumindo-se que um algoritmo está correto, ele pode ter seu desempenho avaliado de acordo com sua complexidade temporal, que normalmente é uma função do tamanho de sua entrada. Quanto maior for a complexidade do algoritmo, pior é o seu desempenho em termos do tempo que se leva para executá-lo em uma máquina. Por exemplo, se seu problema é ordenar um conjunto de N números inteiros, pode-se trivialmente construir um algoritmo cuja complexidade é da ordem de N^2 (polinomial de grau 2), isto é, no pior caso compara-se cada elemento com todo outro. Um algoritmo melhor, já amplamente conhecido para este problema (Heapsort, veja imagem ao lado), é capaz de construir a lista ordenada de N inteiros com complexidade da ordem de N*log(N). Problemas de complexidade similar são agrupados em classes de complexidade.  Para fins de nossa discussão, destacamos duas classes de complexidade: P e NP.

Os problemas da classe NP são problemas de decisão (aqueles em que a resposta são do tipo “sim” ou “não”) que podem ter uma solução verificada em tempo polinomial em uma máquina de Turing determinística. É a mesma coisa que dizer que eles formam a classe de problemas cujas soluções (respostas “sim”) podem ser encontradas em tempo polinomial em uma máquina de Turing não-determinística. Tome como exemplo aquele do fim da seção anterior. Se você me apresentar uma possível solução, eu posso muito rapidamente (tempo polinomial) testar se sua solução é aceita ou não usando um algoritmo determinístico. E se você me pedir o conjunto das soluções que são aceitas, eu também posso te dar uma resposta muito rapidamente (em tempo polinomial) usando uma máquina de Turing não-determinística, embora esta seja um dispositivo meramente teórico.

Os problemas P são problemas de decisão que herdam as características dos problemas NP, isto é, são seu subconjunto. Significa que eles também têm soluções verificadas em tempo polinomial em uma MT determinística e soluções geradas em tempo polinomial em uma MT não-determinística. A particularidade dos problemas da classe P é que eles também podem ser resolvidos (i.e. ter as soluções geradas) em tempo polinomial em uma MT determinística.

O problema de ordenação de inteiros que mencionei é um problema NP e também P. Já o problema de satisfação de restrições do “teste de Einstein” é um problema NP, mas não se sabe se é P, porque até hoje não se construiu um algoritmo determinístico que resolva o problema em tempo polinomial, apenas em tempo exponencial. Existe ainda a classe de problemas NP-hard, que se sabe serem tão difíceis de serem resolvidos quanto o pior problema NP, mas que podem não ser NP (por exemplo, o problema da parada, que nem é decidível — isto é, quando a MT eventualmente não pára). Também tem a classe de problemas chamada de NP-completo, onde encontramos os piores problemas NP (e que não se sabe se é P), para o quais todo problema NP é redutível em tempo polinomial. A consequência que importa é a seguinte: se você achar um algoritmo determinístico de tempo polinomial para resolver um problema NP-completo, então P=NP!

P=NP?
P=NP?

Eu estou com a péssima sensação de que se você, leitor, não tem formação em Computação o texto que escrevi até agora não foi muito claro. Mas tudo bem, é melhor ter tentado do que não. Espero que tenha captado pelo menos a intuição que diferencia uma máquina determinística de uma não-determinística, isto porque…

Uma máquina do tempo pode ser o principal componente de uma máquina de Turing não-determinística

Suponha a seguinte situação: um programa de computador — que representa um algoritmo determinístico que calcula o resultado de uma computação para um problema NP-completo de complexidade exponencial — é executado e apresenta o resultado em 10 anos, exatamente. Logo em seguida, o resultado é submetido a uma máquina do tempo que se encarrega de gravá-lo da região de memória destinada à resposta do mesmo programa no mesmo computador há 10 anos atrás.

Nesta situação, do ponto de vista do usuário deste programa, ele é executado e imediatamente obtém a resposta (tempo constante, que é polinomial de grau zero). Neste caso, este computador mais a máquina do tempo é equivalente a uma máquina de Turing não-determinística. E embora a máquina de Turing não-determinística não seja nenhuma novidade na teoria, neste caso ela se torna implementável na prática.

O mais importante: note que isso não prova que P=NP…

Então…

Ainda que a viagem no tempo exista, não é possível dizer se P=NP, nem o contrário. Mas, na prática, isso não será tão importante quanto hoje, cujo principal motivo de investigação é o desempenho computacional. Como a máquina do tempo é tão teórica quanto a máquina de Turing não-determinística, não dá pra dizer se algum dia ela será construída. Se ela for construída, mesmo que com poder para transportar poucos bits por vez, será revolucionária, e toda computação será realizada nestas máquinas não-determinísticas que, apesar de terem expressividade similar às determinísticas, são muito mais poderosas do ponto de vista do desempenho observado pelo usuário.

É como um cartão de crédito: você usufrui logo do benefício, mas paga depois. No exemplo do parágrafo anterior, o computador que executa o programa ainda terá que executá-lo por 10 anos. Se você pode dar uma garantia de que nada acontecerá nesta execução durante os próximos 10 anos, é possível obter a resposta de imediato. Também haveria limites: não adianta tentar executar algo que gastaria os recursos de um tempo superior ao tempo de vida previsto do planeta Terra, por exemplo… Pois a computação terá sido interrompida pelo fim do planeta! Claro, há maneiras de contornar isso: por exemplo, mandando executar o programa no espaço. Mas, sinceramente, conseguir essas garantias seria muito difícil: garantir 10 anos de execução para resultados imediatos já está de bom tamanho.

Eu ainda não consegui chegar no nível de reflexão que me permita dizer se uma máquina do tempo é capaz de resolver problemas indecidíveis. Eu tenho uma forte intuição de que não. Pensando no problema da parada, e no caso em que a máquina de Turing não pára, não há máquina do tempo que possa ficar infinitamente esperando um resultado que nunca será gerado. Mas, no caso em que pára dentro dos limites de existência do computador, a resposta “sim” vem de imediato.

Quão estranho seria isso para você?

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s