A versão original de esta história apareceu em Quanta revista.
Faça uma pergunta para uma bola mágica de 8, e ela responderá sim, não ou algo irritantemente indeciso. Pensamos nisso como um brinquedo infantil, mas os cientistas teóricos da computação empregam uma ferramenta semelhante. Eles costumam imaginar que podem consultar dispositivos hipotéticos chamados oráculos que podem instantaneamente e corretamente responderem a perguntas específicas. Esses experimentos fantasiosos de pensamento inspiraram novos algoritmos e ajudaram os pesquisadores a mapear o cenário da computação.
Os pesquisadores que invocam oráculos trabalham em um subcampo de ciência da computação chamada teoria da complexidade computacional. Eles estão preocupados com a dificuldade inerente dos problemas, como determinar se um número é primo ou encontrar o caminho mais curto entre dois pontos em uma rede. Alguns problemas são fáceis de resolver, outros parecem muito mais difíceis, mas têm soluções fáceis de verificar, enquanto outros ainda são fáceis para computadores quânticos Mas aparentemente difícil para os comuns.
Os teóricos da complexidade querem entender se essas aparentes diferenças de dificuldade são fundamentais. Existe algo intrinsecamente difícil em certos problemas, ou simplesmente não somos inteligentes o suficiente para encontrar uma boa solução? Os pesquisadores abordam essas questões classificando problemas em “classes de complexidade”-Todos os problemas fáceis vão em uma classe, por exemplo, e todos os problemas fáceis de verificar serem em outro-e provando teoremas sobre as relações entre essas classes.
Infelizmente, o mapeamento do cenário da dificuldade computacional acabou sendo difícil. Assim, em meados da década de 1970, alguns pesquisadores começaram a estudar o que aconteceria se as regras da computação fossem diferentes. É aí que entra os oráculos.
Como o Magic 8 Balls, Oracles são dispositivos que respondem imediatamente a perguntas de sim ou não sem revelar nada sobre seus trabalhos internos. Ao contrário de Magic 8 Balls, eles sempre dizem sim ou não, e estão sempre corretos – uma vantagem de ser fictício. Além disso, um dado Oracle só responderá a um tipo específico de pergunta, como “Este número é Prime?”
O que torna esses dispositivos fictícios úteis para entender o mundo real? Em resumo, eles podem revelar conexões ocultas entre diferentes classes de complexidade.
Pegue as duas classes de complexidade mais famosas. Há a classe de problemas fáceis de resolver, que os pesquisadores chamam de “p” e a classe de problemas que são fáceis de verificar, que os pesquisadores chamam de “NP”. Todos os problemas fáceis de verificar também são fáceis de resolver? Se sim, isso significaria que o NP seria igual a P, e toda a criptografia seria fácil de quebrar (entre outras consequências). Os teóricos da complexidade suspeitam que o NP não seja igual a P, mas não podem provar isso, mesmo que estejam tentando definir o relacionamento entre as duas classes para mais de 50 anos.
Os Oracles os ajudaram a entender melhor o que estão trabalhando. Os pesquisadores inventaram oráculos que respondem a perguntas que ajudam a resolver muitos problemas diferentes. Em um mundo em que todo computador tinha uma linha direta para um desses oráculos, todos os problemas fáceis de verificar também seriam fáceis de resolver e P seria igual ao NP. Mas outros oráculos menos úteis têm o efeito oposto. Em um mundo preenchido por esses oráculos, P e NP seriam prováveis.
