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.[1]
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.[2]
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][1].
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 dologaritmo 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.[3] 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.[4] 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.[5]
Notas[editar | editar código-fonte]
- ↑ «ACM-SIGACT 2007 Gödel Prize». Consultado em 10 de julho de 2015. Arquivado do original em 3 de março de 2016
- ↑ A. A. Razborov and S. Rudich (1997). «Natural proofs». Journal of Computer and System Sciences. 55: 24–35. doi:10.1006/jcss.1997.1494
- ↑ https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#tc0
- ↑ http://dl.acm.org/citation.cfm?id=972643
- ↑ K. Regan (outubro de 2002). «Understanding the Mulmuley-Sohoni Approach to P vs. NP» (PDF). Bulletin of the European Association for Theoretical Computer Science. 78: 86–97
Referências[editar | editar código-fonte]
- A. A. Razborov (2004). «Feasible Proofs and Computations: Partnership and Fusion». Proceedings of the 31st ICALP. Col: Lecture Notes in Computer Science. 3142. [S.l.: s.n.] pp. 8–14 (Draft)
- Lance Fortnow (10 de maio de 2006). «The Importance of Natural Proofs»
- Chow, Timothy Y. (2011), «WHAT IS... a Natural Proof?» (PDF), AMS, Notices, 58 (11), consultado em 5 de agosto de 2014