MIP * = RE não é um erro de digitação. É uma descoberta inovadora e o título cativante de um artigo recente no campo da teoria da complexidade quântica. A teoria da complexidade é um zoológico de “classes de complexidade” – coleções de problemas computacionais – das quais MIP * e RE são apenas duas.
O artigo de 165 páginas mostra que essas duas classes são iguais. Isso pode parecer um detalhe insignificante em uma teoria abstrata sem qualquer aplicação no mundo real. Mas físicos e matemáticos estão se aglomerando para visitar o zoológico, embora provavelmente não entendam tudo. Porque a descoberta tem consequências surpreendentes para suas próprias disciplinas.
Em 1936, Alan Turing mostrou que o problema da parada – decidir algoritmicamente se um programa de computador deve ser interrompido ou executado para sempre – não pode ser resolvido. A ciência da computação moderna nasceu. Seu sucesso deu a impressão de que logo todos os problemas práticos cederiam ao tremendo poder do computador.
Mas logo ficou claro que, embora alguns problemas possam ser resolvidos por meio de algoritmos, o cálculo real vai durar muito depois de nosso Sol ter engolfado o computador que executa o cálculo. Descobrir como resolver um problema por meio de algoritmos não era suficiente. Era vital classificar as soluções por eficiência. A teoria da complexidade classifica os problemas de acordo com a dificuldade de resolvê-los. A dureza de um problema é medida em termos de quanto tempo dura o cálculo.
RE significa problemas que podem ser resolvidos por um computador. É o zoológico. Vamos dar uma olhada em algumas subclasses.
A classe P consiste em problemas que um algoritmo conhecido pode resolver rapidamente (tecnicamente, em tempo polinomial). Por exemplo, multiplicar dois números pertence a P, uma vez que a multiplicação longa é um algoritmo eficiente para resolver o problema. O problema de encontrar os fatores primos de um número não é conhecido por estar em P; o problema pode certamente ser resolvido por um computador, mas nenhum algoritmo conhecido pode fazer isso com eficiência. Um problema relacionado, decidir se um determinado número é primo, estava em um limbo semelhante até 2004, quando um algoritmo eficiente mostrou que esse problema está em P.
Outra classe de complexidade é NP. Imagine um labirinto. “Existe uma maneira de sair deste labirinto?” é uma pergunta sim / não. Se a resposta for sim, então existe uma maneira simples de nos convencer: basta nos dar as direções, nós as seguiremos e encontraremos a saída. Se a resposta for não, entretanto, teremos que percorrer todo o labirinto sem nunca encontrar uma saída para nos convencer.
Esses problemas sim / não para os quais, se a resposta for sim, podemos demonstrar que isso é eficaz, pertencem ao NP. Qualquer solução para um problema serve para nos convencer da resposta e, portanto, P está contido em NP. Surpreendentemente, uma pergunta de um milhão de dólares é se P = NP. Ninguém sabe.
Confie nas máquinas
As classes descritas até agora representam problemas enfrentados por um computador normal. Mas os computadores estão mudando fundamentalmente – os computadores quânticos estão sendo desenvolvidos. Mas se um novo tipo de computador surgir e alega resolver um de nossos problemas, como podemos confiar que ele está correto?
Imagine uma interação entre duas entidades, um interrogador e um provador. Em um interrogatório policial, o provador pode ser um suspeito que está tentando provar sua inocência. O interrogador deve decidir se o provador é suficientemente convincente. Existe um desequilíbrio; em termos de conhecimento, o interrogador está em uma posição inferior.
Na teoria da complexidade, o interrogador é a pessoa, com poder computacional limitado, que tenta resolver o problema. O provador é o novo computador, que supostamente possui um imenso poder computacional. Um sistema de prova interativo é um protocolo que o interrogador pode usar a fim de determinar, pelo menos com alta probabilidade, se o provador deve ser acreditado. Por analogia, são crimes que a polícia pode não ser capaz de resolver, mas pelo menos inocentes podem convencer a polícia de sua inocência. Este é o IP da classe.
Se vários provadores puderem ser interrogados e os provadores não tiverem permissão para coordenar suas respostas (como normalmente é o caso quando a polícia interroga vários suspeitos), então chegamos à classe MIP. Esses interrogatórios, por meio do exame cruzado das respostas dos provadores, fornecem ao interrogador maior poder, de modo que o MIP contém IP.
A comunicação quântica é uma nova forma de comunicação realizada com qubits. Emaranhamento – um recurso quântico no qual os qubits estão assustadoramente emaranhados, mesmo se separados – torna a comunicação quântica fundamentalmente diferente da comunicação comum. Permitir que os provadores de MIP compartilhem um qubit emaranhado leva à classe MIP *.
Parece óbvio que a comunicação entre os provadores só pode servir para ajudar os provadores a coordenar mentiras, em vez de ajudar o interrogador a descobrir a verdade. Por esse motivo, ninguém esperava que permitir mais comunicação tornaria os problemas computacionais mais confiáveis e solucionáveis. Surpreendentemente, agora sabemos que MIP * = RE. Isso significa que a comunicação quântica se comporta de maneira totalmente diferente da comunicação normal.
Implicações de longo alcance
Na década de 1970, Alain Connes formulou o que ficou conhecido como o problema de incorporação de Connes. Grosseiramente simplificado, perguntava se matrizes infinitas podem ser aproximadas por matrizes finitas. Este novo artigo agora provou que isso não é possível – uma descoberta importante para matemáticos puros.
Em 1993, entretanto, Boris Tsirelson identificou um problema na física agora conhecido como Problema de Tsirelson. Tratava-se de dois formalismos matemáticos diferentes de uma única situação na mecânica quântica – até agora uma teoria incrivelmente bem-sucedida que explica o mundo subatômico. Sendo duas descrições diferentes do mesmo fenômeno, era de se esperar que os dois formalismos fossem matematicamente equivalentes.
Mas o novo jornal agora mostra que não. Não se sabe exatamente como ambos podem produzir os mesmos resultados e descrever a mesma realidade física, mas é por isso que os físicos também estão repentinamente se interessando.
O tempo dirá que outras questões científicas sem resposta renderão ao estudo da complexidade. Sem dúvida, MIP * = RE é um grande salto em frente.
Publicado em 19/08/2020 07h07
Artigo original:
Estudo original:
Achou importante? Compartilhe!
Assine nossa newsletter e fique informado sobre Astrofísica, Biofísica, Geofísica e outras áreas. Preencha seu e-mail no espaço abaixo e clique em “OK”: