DBpedia – Linked Data Fragments

Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Yaos_principle> ?p ?o }

• Yaos_principle abstract "In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of a randomized algorithm on the worst case input, is no better than a worst-case random probability distribution of the deterministic algorithm which performs best for that distribution. Thus, to establish a lower bound on the performance of randomized algorithms, it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution. This principle is named after Andrew Yao, who first proposed it.Yao's principle may be interpreted in game theoretic terms, via a two-player zero sum game in which one player, Alice, selects a deterministic algorithm, the other player, Bob, selects an input, and the payoff is the cost of the selected algorithm on the selected input. Any randomized algorithm R may be interpreted as a randomized choice among deterministic algorithms, and thus as a strategy for Alice. By von Neumann's minimax theorem, Bob has a randomized strategy that performs at least as well against R as it does against the best pure strategy Alice might choose; that is, Bob's strategy defines a distribution on the inputs such that the expected cost of R on that distribution (and therefore also the worst case expected cost of R) is no better than the expected cost of any single deterministic algorithm against the same distribution.".
• Yaos_principle wikiPageExternalLink favorite-theorems-yao-principle.html.
• Yaos_principle wikiPageID "4835703".
• Yaos_principle wikiPageLength "4328".
• Yaos_principle wikiPageOutDegree "19".
• Yaos_principle wikiPageRevisionID "673092899".
• Yaos_principle wikiPageWikiLink Alice_and_Bob.
• Yaos_principle wikiPageWikiLink Andrew_Yao.
• Yaos_principle wikiPageWikiLink Best,_worst_and_average_case.
• Yaos_principle wikiPageWikiLink Category:Computational_complexity_theory.
• Yaos_principle wikiPageWikiLink Category:Randomness.
• Yaos_principle wikiPageWikiLink Computational_complexity_theory.
• Yaos_principle wikiPageWikiLink Deterministic_algorithm.
• Yaos_principle wikiPageWikiLink Expected_value.
• Yaos_principle wikiPageWikiLink Fubinis_theorem.
• Yaos_principle wikiPageWikiLink Game_theory.
• Yaos_principle wikiPageWikiLink John_von_Neumann.
• Yaos_principle wikiPageWikiLink Las_Vegas_algorithm.
• Yaos_principle wikiPageWikiLink Minimax.
• Yaos_principle wikiPageWikiLink Minimax_theorem.
• Yaos_principle wikiPageWikiLink Monte_Carlo_algorithm.
• Yaos_principle wikiPageWikiLink Pigeonhole_principle.
• Yaos_principle wikiPageWikiLink Probability_distribution.
• Yaos_principle wikiPageWikiLink Randomized_algorithm.
• Yaos_principle wikiPageWikiLink Worst_case.
• Yaos_principle wikiPageWikiLink Zero-sum_game.
• Yaos_principle wikiPageWikiLink Zero_sum_game.
• Yaos_principle wikiPageWikiLinkText "Yao's principle".
• Yaos_principle hasPhotoCollection Yaos_principle.
• Yaos_principle wikiPageUsesTemplate Template:Citation.
• Yaos_principle wikiPageUsesTemplate Template:Cite_web.
• Yaos_principle subject Category:Computational_complexity_theory.
• Yaos_principle subject Category:Randomness.
• Yaos_principle comment "In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of a randomized algorithm on the worst case input, is no better than a worst-case random probability distribution of the deterministic algorithm which performs best for that distribution.".
• Yaos_principle label "Yao's principle".
• Yaos_principle sameAs הלמה_של_יאו.
• Yaos_principle sameAs m.0cq70h.
• Yaos_principle sameAs Q8049023.
• Yaos_principle sameAs Q8049023.
• Yaos_principle wasDerivedFrom Yaos_principleoldid=673092899.
• Yaos_principle isPrimaryTopicOf Yaos_principle.