About: Natural proof

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

Provides lower bounds on the circuit complexity of boolean functions

Property	Value
dbo:description	concept en informatique théorique (fr) provides lower bounds on the circuit complexity of boolean functions (en)
dbo:wikiPageExternalLink	http://www.mi.ras.ru/~razborov/icalp_lics.ps https://complexityzoo.net/Complexity_Zoo:A%23ac0m http://weblog.fortnow.com/2006/05/importance-of-natural-proofs.html https://www.ams.org/notices/201111/rtx111101586p.pdf
dbo:wikiPageWikiLink	dbr:Pseudorandom_function_family dbr:Discrete_logarithm dbr:P_versus_NP_problem dbr:Truth_table dbc:Computational_complexity_theory dbr:Gödel_Prize dbr:Circuit_complexity dbr:Alexander_Razborov dbr:Avi_Wigderson dbr:Steven_Rudich dbr:Computational_complexity_theory dbr:Boolean_satisfiability_problem dbr:Complexity_class dbr:TC0 dbr:P/poly dbr:AC0 dbr:Boolean_function dbr:Naor-Reingold_Pseudorandom_Function dbr:P_=_NP_problem dbr:Elliptic_curve_cryptography
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_web dbt:Citation dbt:Short_description
dct:subject	dbc:Computational_complexity_theory
gold:hypernym	dbr:Kind
rdfs:label	Natural proof (en) Preuve naturelle (fr) 自然な証明 (ja) Prova natural (pt)
owl:sameAs	freebase:Natural proof wikidata:Natural proof dbpedia-fr:Natural proof dbpedia-ja:Natural proof dbpedia-pt:Natural proof dbpedia-global:Natural proof dbr:Natural proof
prov:wasDerivedFrom	wikipedia-en:Natural_proof?oldid=1292253421&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Natural_proof
is dbo:wikiPageRedirects of	dbr:Natural_proofs
is dbo:wikiPageWikiLink of	dbr:List_of_computability_and_complexity_topics dbr:P_versus_NP_problem dbr:Gödel_Prize dbr:Circuit_complexity dbr:Alexander_Razborov dbr:Steven_Rudich dbr:Pseudorandom_generator dbr:List_of_mathematical_logic_topics dbr:List_of_Russian_IT_developers dbr:Geometric_complexity_theory dbr:Natural_proofs
is dbp:notableIdeas of	dbr:Steven_Rudich
is foaf:primaryTopic of	wikipedia-en:Natural_proof

This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International