Description
Algorithms are inherently deterministic. Here is a famous non deterministic algorithm: “When you come to a fork in the road, take it,” by Yogi Berra, the American baseball player and unlicensed philosopher, In our view, “nondeterministic algorithm” is a contradiction in terms. Yet there are useful probabilistic and quantum algorithms that are inherently non deterministic. How do they work? Our thesis is that non-algorithmic work — from tossing a coin to quantum measurement — is done by assistants, partners, oracles. We present the theory of assisted algorithms. Our running example is quantum, but no knowledge of quantum computing is assumed.
Speaker: Yuri Gurevich
Host: Nikolaj Bjorner
See more at https://www.microsoft.com/en-us/research/video/assisted-algorithms/