Depois de Turing, os cientistas da computação começaram a classificar outros problemas por sua dificuldade. Problemas mais difíceis exigem mais recursos computacionais para serem resolvidos – mais tempo de execução, mais memória. Este é o estudo da complexidade computacional.

Por fim, todo problema apresenta duas grandes questões: “Quão difícil é resolver?” e “Quão difícil é verificar se uma resposta está correta?”

Interrogar para verificar

Quando os problemas são relativamente simples, você mesmo pode verificar a resposta. Mas quando elas ficam mais complicadas, até verificar uma resposta pode ser uma tarefa esmagadora. No entanto, em 1985, os cientistas da computação perceberam que é possível desenvolver a confiança de que uma resposta está correta mesmo quando você não pode confirmá-la.

O método segue a lógica de um interrogatório policial.

Se um suspeito conta uma história elaborada, talvez você não possa ir ao mundo para confirmar todos os detalhes. Mas, fazendo as perguntas certas, você pode pegar o seu suspeito em uma mentira ou desenvolver a confiança de que a história é verdadeira.

Em termos de ciência da computação, as duas partes em um interrogatório são um computador poderoso que propõe uma solução para um problema – conhecido como provador – e um computador menos poderoso que deseja fazer perguntas ao provador para determinar se a resposta está correta. Este segundo computador é chamado de verificador.

Para dar um exemplo simples, imagine que você é daltônico e outra pessoa, o provador, afirma que duas bolas de gude são de cores diferentes. Você não pode verificar essa afirmação sozinho, mas, através de um interrogatório inteligente, ainda pode determinar se é verdade.

Coloque as duas bolinhas nas costas e misture-as. Em seguida, peça ao provador para lhe dizer qual é qual. Se elas realmente são de cores diferentes, o provador deve responder à pergunta corretamente todas as vezes. Se os mármores são na verdade da mesma cor – o que significa que parecem idênticos – o provador vai adivinhar errado na metade do tempo.

“Se vejo você ter sucesso mais da metade do tempo, tenho certeza de que eles não são” da mesma cor, disse Vidick.

Ao fazer perguntas a um provador, você pode verificar as soluções para uma classe mais ampla de problemas do que pode sozinho.

Em 1988, os cientistas da computação consideraram o que acontece quando dois provadores propõem soluções para o mesmo problema. Afinal, se você tem dois suspeitos para interrogar, é ainda mais fácil resolver um crime ou verificar uma solução, pois você pode jogá-los um contra o outro.

“Dá mais alavancagem ao verificador. Você interroga, faz perguntas relacionadas, verifica as respostas ”, disse Vidick. Se os suspeitos estão dizendo a verdade, suas respostas devem se alinhar na maior parte do tempo. Se eles estão mentindo, as respostas entrarão em conflito com mais frequência.

Da mesma forma, os pesquisadores mostraram que, ao interrogar dois provadores separadamente sobre suas respostas, é possível verificar rapidamente soluções para uma classe de problemas ainda maior do que quando você tem apenas um provador para interrogar.

A complexidade computacional pode parecer inteiramente teórica, mas também está intimamente ligada ao mundo real. Os recursos que os computadores precisam para resolver e verificar problemas – tempo e memória – são fundamentalmente físicos. Por esse motivo, novas descobertas na física podem mudar a complexidade computacional.

“Se você escolher um conjunto diferente de física, como o quantum e não o clássico, obterá uma teoria da complexidade diferente”, disse Natarajan.

A nova prova é o resultado final dos cientistas da computação do século XXI que enfrentam uma das idéias mais estranhas da física do século XX: emaranhamento.

A conjectura de incorporação de Connes

Quando duas partículas são emaranhadas, elas realmente não se afetam – elas não têm relação causal. Einstein e seus co-autores elaboraram essa idéia em seu artigo de 1935. Posteriormente, físicos e matemáticos tentaram criar uma maneira matemática de descrever o que o envolvimento realmente significava.

No entanto, o esforço saiu um pouco confuso. Os cientistas criaram dois modelos matemáticos diferentes para entrelaçamento – e não ficou claro que eles eram equivalentes entre si.



Fonte