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 2n  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 AC0. 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 AC0-não podem ser úteis contra AC0[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 TC0 de circuitos de limiar de profundidade constante e tamanho polinomial, que acredita-se ser menor que P/polinomial.https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#tc0  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 TC0.http://dl.acm.org/citation.cfm?id=972643 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.

Notas

Referências (Draft)

Categoria:Complexidade