Randomized algorithms as zero-sum games
Randomized algorithms are algorithms that employ a degree of randomness as part of their logic. These algorithms can be used to give good average-case results (complexity-wise) to problems which are hard to solve deterministically, or display poor worst-case complexity. An algorithmic game theoretic approach can help explain why in the average case randomized algorithms may work better than deterministic algorithms.
- Comment
- enRandomized algorithms are algorithms that employ a degree of randomness as part of their logic. These algorithms can be used to give good average-case results (complexity-wise) to problems which are hard to solve deterministically, or display poor worst-case complexity. An algorithmic game theoretic approach can help explain why in the average case randomized algorithms may work better than deterministic algorithms.
- Has abstract
- enRandomized algorithms are algorithms that employ a degree of randomness as part of their logic. These algorithms can be used to give good average-case results (complexity-wise) to problems which are hard to solve deterministically, or display poor worst-case complexity. An algorithmic game theoretic approach can help explain why in the average case randomized algorithms may work better than deterministic algorithms.
- Hypernym
- Algorithms
- Is primary topic of
- Randomized algorithms as zero-sum games
- Label
- enRandomized algorithms as zero-sum games
- Link from a Wikipage to another Wikipage
- Average case complexity
- Category:Non-cooperative games
- Category:Randomized algorithms
- Complexity analysis
- Deterministic algorithm
- Expected value
- Game theory
- John von Neumann
- Minimax
- Mixed strategy
- Probability distribution
- Quick sort
- Randomized algorithm
- Randomized algorithms
- Strategy (game theory)
- Worst-case
- Yao's principle
- Zero-sum game
- SameAs
- 4tvmR
- m.0b6g3n
- Q7292008
- Randomized algorithms as zero-sum games
- Subject
- Category:Non-cooperative games
- Category:Randomized algorithms
- WasDerivedFrom
- Randomized algorithms as zero-sum games?oldid=1063823237&ns=0
- WikiPageLength
- 2755
- Wikipage page ID
- 26009171
- Wikipage revision ID
- 1063823237
- WikiPageUsesTemplate
- Template:Unreferenced