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 - dos quais MIP ^* e RE são apenas dois.

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 reunindo para visitar o zoológico, mesmo que eles 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 em loop 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 renderiam-se ao tremendo poder do computador.

Mas logo ficou claro que, embora alguns problemas possam ser resolvidos algoritmicamente, a computação real vai durar muito depois que nosso Sol tiver engolfado o computador que está fazendo a computação. 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, pois 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 é sim, então há uma maneira simples de nos convencer:simplesmente nos dê as instruções, nós os seguiremos, e vamos encontrar a saída. Se a resposta for não, Contudo, teríamos que atravessar todo o labirinto sem nunca encontrar uma saída para sermos convencidos.

Esses sim / não problemas para os quais, Se a resposta é sim, podemos demonstrar isso de forma eficiente, pertencem ao NP. Qualquer solução para um problema serve para nos convencer da resposta, e então 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 aparecer e alegar que resolve um dos nossos problemas, como podemos confiar que 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 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, tentando resolver o problema. O provador é o novo computador, que se supõe ter um imenso poder computacional. Um sistema de prova interativo é um protocolo que o interrogador pode usar para 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 podem ser interrogados, e os provadores não têm 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 mais poder, então MIP contém IP.

A comunicação quântica é uma nova forma de comunicação realizada com qubits. Emaranhamento - um recurso quântico em que os qubits estão assustadoramente emaranhados, mesmo se separado - 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ó podem servir para ajudar os provadores a coordenar mentiras, em vez de ajudar o interrogador a descobrir a verdade. Por essa razão, 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. Totalmente simplificado, isso perguntou 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, Enquanto isso, 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é hoje 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. Exatamente como eles podem produzir os mesmos resultados e ambos descreverem a mesma realidade física é desconhecido, 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.

Este artigo foi republicado de The Conversation sob uma licença Creative Commons. Leia o artigo original.