Por que a aleatoriedade é um problema? (ou seja, por que nos preocupamos com a des randomização?)

Estou lendo a pesquisa de Aaronson sobre P vs. NP, e entendi que, na teoria da CS, as pessoas realmente se preocupam com resultados de des aleatorização, como P vs. BPP etc. Minha pergunta é: qual é o problema da aleatoriedade? Se seu algoritmo exigir apenas um número polinomial de bits aleatórios, basta pedir a um físico para obter os bits para você, o que não é um problema, pois você só precisa de um número tratável e, em seguida, escreva-os no Turing máquina de fita e você é bom! O objetivo da teoria da complexidade é descobrir o que podemos computar neste universo, certo? Bem, esse universo tem aleatoriedade, certo? Então, por que nos preocupamos com a des randomização? Respostas teóricas e práticas são bem-vindas.

A teoria da complexidade é uma teoria matemática que visa abordar uma deficiência da teoria da computabilidade, ou seja, leva em consideração o uso de recursos. Embora seja verdade que, em seus primeiros dias, visava capturar a noção de "computação prática" (mesmo sabores específicos, como computação paralela, supostamente capturada por NC), ela se separou e se afastou da realidade. Como exemplo, você pode executar etapas mais altas na hierarquia polinomial, classes de maior complexidade, como PSPACE, classes definidas usando alternância e assim por diante. De fato, grande parte desse material data dos primeiros dias da teoria da complexidade, mostrando que ele perdeu o contato com a realidade rapidamente.

Tradicionalmente, os dois recursos mais importantes estudados pela teoria da complexidade são tempo e espaço. No entanto, outros recursos também interessaram aos teóricos da complexidade, por exemplo, alternância e aleatoriedade (sem mencionar o mundo da complexidade do circuito). Filosoficamente falando, é uma questão fascinante se a aleatoriedade reduz drasticamente o tempo de computação de alguns problemas ou se o ganho é apenas polinomial (como sugerido pela conjectura P = BPP). No entanto, parece não ter nenhuma relevância prática, embora não seja pelo motivo que você mencionou. Na prática, não há necessidade de aleatoriedade física real (exceto para fins criptográficos), e os geradores de números pseudo-aleatórios funcionam bem o suficiente.

Não sou especialista em teoria da complexidade, mas acho que há razões práticas para se interessar por essa questão.

1. Como observado por Derek Elkins, na verdade, produzir números aleatórios "físicos" é bastante difícil, e produzir a distribuição certa com a quantidade certa de entropia em velocidade suficiente é difícil o suficiente para justificar sites e hardware personalizado . Seria bom saber que isso pode ser evitado, pelo menos em teoria.

2. Na física clássica, não há aleatoriedade "verdadeira", apenas as leis físicas (determinísticas) e as condições iniciais do sistema (ou de todo o universo, eu acho). É uma questão filosófica interessante se essa aleatoriedade é equivalente à verdadeira aleatoriedade em algum sentido. Esta pergunta encontra respostas nos campos da teoria do caos , da teoria dos processos ergódicos e da ciência da computação, em questões como P vs BPP.

3. A questão de saber se podemos simular com precisão a aleatoriedade em P vs BPP parece muito relacionada à questão de saber se podemos realmente criptografar, por exemplo, a existência de alçapões ou funções de mão única . Em particular, a capacidade de produzir deterministicamente bits que "parecem aleatórios" o suficiente para qualquer algoritmo específico parece ser um bom pré-requisito para encontrar uma função criptográfica que criptografa uma determinada mensagem em um fluxo de bits indistinguível de bits aleatórios, se a chave não for conhecida. . Portanto, resolver a questão muito difícil da existência de funções unidirecionais deve exigir a solução de P vs BPP ao longo do caminho.