Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Natural_proof> ?p ?o }
Showing triples 1 to 48 of
48
with 100 triples per page.
- Natural_proof 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.The notion of natural proofs was introduced by Alexander Razborov and Steven Rudich in their article Natural proofs, first presented in 1994, and later published in 1997, for which they received the 2007 Gödel Prize.Specifically, natural proofs prove lower bounds on the circuit complexity of boolean functions. A natural proof shows, either directly or indirectly, that a boolean function has a certain natural combinatorial property. Under the assumption that pseudorandom functions exist with "exponential hardness" as specified in their main theorem, Razborov and Rudich show that these proofs cannot separate certain complexity classes. Notably, assuming pseudorandom functions exist, these proofs cannot separate the complexity classes P and NP.For example, their article states:[...] consider a commonly envisioned proof strategy for proving P ≠ NP: Formulate some mathematical notion of "discrepancy" or "scatter" or "variation" of the values of a Boolean function, or of an associated polytope or other structure. [...] Show by an inductive argument that polynomial-sized circuits can only compute functions of "low" discrepancy. [...] Then show that SAT, or some other function in NP, has "high" discrepancy.Our main theorem in Section 4 gives evidence that no proof strategy along these lines can ever succeed.A property of boolean functions is defined to be natural if it contains a property meeting the constructivity and largeness conditions defined by Razborov and Rudich. Roughly speaking, the constructivity condition requires that a property be decidable in (quasi-)polynomial time when the 2n-sized truth table of an n-input boolean function is given as input, asymptotically as n increases. This is the same as time singly exponential in n. Properties that are easy to understand are likely to satisfy this condition. The largeness condition requires that the property hold for a sufficiently large fraction of the set of all boolean functions.A property is useful against a complexity class C if every sequence of boolean functions having the property infinitely often defines a language outside of C. A natural proof is a proof that establishes that a certain language lies outside of C and refers to a natural property that is useful against C.Razborov and Rudich give a number of examples of lower-bound proofs against classes C smaller than P/poly that can be "naturalized", i.e. converted into natural proofs. An important example treats proofs that the parity problem is not in the class AC0. They give strong evidence that the techniques used in these proofs cannot be extended to show stronger lower bounds. In particular, AC0-natural proofs cannot be useful against AC0[m].Razborov and Rudich also reproduce Avi Wigderson's unconditional proof that natural proofs cannot prove exponential lower bounds for the discrete logarithm problem.There is strong current belief that the mechanism of this paper actually blocks lower-bound proofs against the complexity class TC0 of constant-depth, polynomial-sized threshold circuits, which is believed but not proven smaller than P/poly. This belief is because, under widely believed conjectures regarding the hardness of factoring in certain elliptic curve groups, there exist exponentially hard pseudorandom functions computable in TC0. However, some researchers believe that the Razborov-Rudich limitations are actually good guidance for what a "super-natural" lower-bound proof might involve, such as properties hard or complete for exponential space.".
- Natural_proof wikiPageExternalLink importance-of-natural-proofs.html.
- Natural_proof wikiPageExternalLink rtx111101586p.pdf.
- Natural_proof wikiPageExternalLink icalp_lics.ps.
- Natural_proof wikiPageExternalLink ac0m.
- Natural_proof wikiPageID "662262".
- Natural_proof wikiPageLength "6031".
- Natural_proof wikiPageOutDegree "19".
- Natural_proof wikiPageRevisionID "677877021".
- Natural_proof wikiPageWikiLink AC0.
- Natural_proof wikiPageWikiLink Alexander_Razborov.
- Natural_proof wikiPageWikiLink Boolean_function.
- Natural_proof wikiPageWikiLink Boolean_satisfiability_problem.
- Natural_proof wikiPageWikiLink Category:Computational_complexity_theory.
- Natural_proof wikiPageWikiLink Circuit_complexity.
- Natural_proof wikiPageWikiLink Complexity_class.
- Natural_proof wikiPageWikiLink Computational_complexity_theory.
- Natural_proof wikiPageWikiLink Discrete_logarithm.
- Natural_proof wikiPageWikiLink Elliptic_curve_cryptography.
- Natural_proof wikiPageWikiLink Gödel_Prize.
- Natural_proof wikiPageWikiLink Naor-Reingold_Pseudorandom_Function.
- Natural_proof wikiPageWikiLink poly.
- Natural_proof wikiPageWikiLink P_=_NP_problem.
- Natural_proof wikiPageWikiLink P_versus_NP_problem.
- Natural_proof wikiPageWikiLink Pseudorandom_function_family.
- Natural_proof wikiPageWikiLink Steven_Rudich.
- Natural_proof wikiPageWikiLink TC0.
- Natural_proof wikiPageWikiLink Truth_table.
- Natural_proof wikiPageWikiLinkText "Natural Proof".
- Natural_proof wikiPageWikiLinkText "Natural Proofs".
- Natural_proof wikiPageWikiLinkText "Natural proof".
- Natural_proof wikiPageWikiLinkText "natural proof".
- Natural_proof hasPhotoCollection Natural_proof.
- Natural_proof wikiPageUsesTemplate Template:Citation.
- Natural_proof wikiPageUsesTemplate Template:Cite_book.
- Natural_proof wikiPageUsesTemplate Template:Cite_web.
- Natural_proof subject Category:Computational_complexity_theory.
- Natural_proof hypernym Kind.
- Natural_proof type Article.
- Natural_proof type Article.
- Natural_proof 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.".
- Natural_proof label "Natural proof".
- Natural_proof sameAs Prova_natural.
- Natural_proof sameAs m.030r95.
- Natural_proof sameAs Q6980761.
- Natural_proof sameAs Q6980761.
- Natural_proof wasDerivedFrom Natural_proof?oldid=677877021.
- Natural_proof isPrimaryTopicOf Natural_proof.