About: Average-case complexity

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

unknown

Property	Value
dbo:wikiPageExternalLink	https://web.archive.org/web/20090214175940/http:/www.itl.nist.gov/div897/sqg/dads/HTML/theta.html http://research.microsoft.com/~gurevich/Opera/76.pdf http://www-cse.ucsd.edu/~russell/average.ps http://www.cs.nyu.edu/csweb/Research/TechReports/TR1995-711/TR1995-711.pdf
dbo:wikiPageWikiLink	dbr:Hamiltonian_path_problem dbr:Association_for_Computing_Machinery dbr:NP_(complexity) dbr:Probability_distribution dbr:Quicksort dbr:Worst-case_complexity dbr:Amortized_analysis dbr:Cryptography dbr:University_of_California,_San_Diego dbr:Probabilistic_analysis_of_algorithms dbr:Algorithm dbr:Donald_Knuth dbr:Leonid_Levin dbr:Best,_worst_and_average_case dbr:Computational_complexity_theory dbr:P_(complexity) dbc:Randomized_algorithms dbr:Derandomization dbr:Randomized_algorithm dbr:Symposium_on_Theory_of_Computing dbr:Integer_factorization dbr:NP-complete dbr:Non-deterministic_Turing_machine dbr:NEXP dbr:NP-complete_problems dbr:EXP dbr:One-way_functions dbr:Discrete_log dbr:Art_of_Computer_Programming dbr:CoNP
dbp:wikiPageUsesTemplate	dbt:Mset dbt:Cite_book dbt:Reflist dbt:Redirect dbt:Math dbt:= dbt:Citation dbt:Sfrac dbt:Mvar dbt:Abs dbt:Pn dbt:Rp
dct:subject	dbc:Analysis_of_algorithms dbc:Randomized_algorithms
gold:hypernym	dbr:Amount
rdfs:label	Average-case complexity (en) Complexité en moyenne des algorithmes (fr) Complexidade de caso médio (pt) Сложность алгоритма в среднем (ru)
owl:sameAs	yago-res:Average-case complexity freebase:Average-case complexity wikidata:Average-case complexity dbpedia-fr:Average-case complexity dbpedia-pt:Average-case complexity dbpedia-fa:Average-case complexity dbpedia-ru:Average-case complexity dbpedia-sr:Average-case complexity dbpedia-global:Average-case complexity
prov:wasDerivedFrom	wikipedia-en:Average-case_complexity?oldid=1296404978&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Average-case_complexity
is dbo:knownFor of	dbr:Leonid_Levin
is dbo:wikiPageRedirects of	dbr:Average_case_complexity dbr:Average_case_computational_complexity dbr:AvgP dbr:Expected_time dbr:DistNP dbr:DistP
is dbo:wikiPageWikiLink of	dbr:Discrete_logarithm dbr:AVGP_(disambiguation) dbr:Partial_sorting dbr:Harmonic_series_(mathematics) dbr:P_versus_NP_problem dbr:Worst-case_complexity dbr:Amortized_analysis dbr:Isolation_lemma dbr:Circuit_complexity dbr:Probabilistic_analysis_of_algorithms dbr:Security_of_cryptographic_hash_functions dbr:Criss-cross_algorithm dbr:Leonid_Levin dbr:Philippe_Flajolet dbr:Best,_worst_and_average_case dbr:Hash_table dbr:Boyer–Moore–Horspool_algorithm dbr:Average_case_complexity dbr:Average_case_computational_complexity dbr:AvgP dbr:Skip_list dbr:DFA_minimization dbr:Jeffrey_Vitter dbr:Time_complexity dbr:Klee–Minty_cube dbr:Random_self-reducibility dbr:Smoothed_analysis dbr:Computational_complexity dbr:Computational_hardness_assumption dbr:Lattice-based_cryptography dbr:Lattice_problem dbr:Generic-case_complexity dbr:Cycle_detection dbr:Indistinguishability_obfuscation dbr:Expected_time dbr:DistNP dbr:DistP
is dbp:knownFor of	dbr:Leonid_Levin
is foaf:primaryTopic of	wikipedia-en:Average-case_complexity