| dbo:abstract
|
- In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture on the existence of pseudorandom functions) that no such proof can possibly be used to solve the P vs. NP problem. (en)
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
- 計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。 (ja)
- 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 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 . 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][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. 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. 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. (pt)
|
| rdfs:comment
|
- In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture on the existence of pseudorandom functions) that no such proof can possibly be used to solve the P vs. NP problem. (en)
- En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP. (fr)
- 計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。 (ja)
- 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. Por exemplo, um trecho do artigo diz: (pt)
|
