# Prova natural

Em complexidade da teoria computacional, uma prova natural é uma certa prova estabelecendo que uma classe de complexidade difere de uma outra. Enquanto essas provas são em algum sentido “natural”, pode ser mostrado (assumindo uma conjectura amplamente acreditada sobre a existência de funções pseudoaleatórias) que nenhuma prova desse tipo pode ser usada para resolver o problema P versus NP.
A noção de provas naturais foi introduzida por Alexander Razborov e Steven Rudich em seu artigo Natural proofs, apresentado pela primeira vez em 1994, e publicado em 1997. Com este artigo eles ganharam em 2007, o prêmio Gödel.
Especificamente, provas naturais provam o limitante inferior sobre a complexidade de circuitos de funções booleanas. Uma prova natural mostra, direta ou indiretamente, que uma função booleana tem uma certa propriedade natural combinatória. Sob a suposição de que funções pseudoaleatórias existem com “dificuldade exponencial” como especificado no principal teorema deles, Razborov e Rudich mostram que essas provas não podem separar certas classes de complexidade. Notadamente, assumindo que funções pseudoaleatórias existem, essas provas não podem separar as classes de complexidade P e NP.
Por exemplo, um trecho do artigo diz:
    [...] considere uma estratégia de prova comumente vislumbrada para provar P ≠ NP:
   * Formule algum conceito matemático de “discrepância” ou “dispersão” ou “variação” de valores de uma função booleana, ou de um polítopo associado ou outra estrutura [...]
   * Mostre por um argumento indutivo que circuitos de tamanho polinomial podem computar somente funções de “baixa” discrepância. [...]
   * Então mostre que SAT, ou alguma outra linguagem em NP, tem “alta” discrepância. Nosso principal teorema na seção 4 dá evidência de que nenhuma estratégia de prova nessa linha pode ter sucesso.
Uma propriedade de funções booleanas é definida como sendo natural se ela contém uma propriedade satisfazendo as condições de construtividade e de grandeza definidas por Razborov e Rudich. Grosso modo, a condição de construtividade requer que uma propriedade seja decidível em tempo (quasi-) polinomial quando a tabela verdade de tamanho 2$^n$ de uma função boleada de n entradas é dada como entrada, assintoticamente à medida que n cresce. Isso é o mesmo que tempo simplesmente exponencial em n. Propriedades que são fáceis de entender são passíveis de satisfazer essa condição. A condição de grandeza requer que uma propriedade se aplique a uma porção suficientemente grande do conjunto de todas as funções booleanas.
Uma propriedade é útil contra uma complexidade C se toda sequencia de funções booleanas tendo a propriedade com frequência infinita define uma linguagem fora de C. Uma prova natural é uma prova que estabelece que uma certa linguagem encontra-se fora de C e se refere a uma propriedade natural que é útil contra C.
Razborov e Rudich deram uma série de exemplos de provas de limitante inferior contra classes C menores que P/polinomial, que podem ser “naturalizadas”, isto é, convertidas em provas naturais. Um importante exemplo trata provas de que o problema da paridade não está na classe AC$^0$. Eles dão uma forte evidência de que as técnicas usada nessas provas não podem ser estendidas para mostrar limitantes inferiores mais fortes. Em particular, provas naturais em AC$^0$-não podem ser úteis contra AC$^0$[m].
Razborov e Rudich também reproduziram a prova incondicional de Avi Wigderson, que diz que provas naturais não podem provar limitantes inferiores exponenciais para o problema do logaritmo discreto.
Existe uma forte crença atual de que o mecanismo deste artigo, na verdade, impede provas de limitantes inferiores contra a classe de complexidade TC$^0$ de circuitos de limiar de profundidade constante e tamanho polinomial, que acredita-se ser menor que P/polinomial. Essa crença é devido ao fato de que, sob conjecturas amplamente acreditadas com respeito à dificuldade de fatoração em certos grupos de curvas elípticas, existem funções pseudoaleatórias exponencialmente difíceis computáveis em TC$^0$. Entretanto, alguns pesquisadores acreditam que as limitações de Razborov-Rudich são na verdade boas orientações para o que uma prova de limitante inferior “super natural” pode envolver, tal como propriedades difíceis ou completas para espaço exponencial.