Yao's principle
id:
yao-s-principle-280-1746244
title:
Yao's principle
text:
In computational complexity theory, Yao's principle is a way to prove lower bounds on the worst-case performance of randomized algorithms, by comparing them to deterministic (non-random) algorithms. It states that, for any randomized algorithm, there exists a probability distribution on inputs to the algorithm, so that the expected cost of the randomized algorithm on its worst-case input is at least as large as the cost of the best deterministic algorithm on a random input from this distribution
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Yao%27s_principle
date created:
date modified:
2022-10-23T18:24:36Z
main entity:
{"identifier":"Q8049023","url":"https://www.wikidata.org/entity/Q8049023"}
image:
fields total:
13
integrity:
13