Felix Weninger

Randomness and Non-uniformity

Abstract

In the first part, we introduce randomized algorithms as a new notion of efficient algorithms for decision problems. We classify randomized algorithms according to their error probabilities, and define appropriate complexity classes. (RP, coRP, ZPP, BPP, PP). We discuss which classes are realistic proposals for design of probabilistic algorithms. We cover the implementation of randomized algorithms using different non-ideal random sources. We introduce the concept of derandomization and the “hardness vs. randomness“ paradigm. Second, we illustrate non-uniform complexity in terms of Boolean circuits and Turing machines that take advice. We demonstrate the power of non-uniform complexity classes. We show the relevance of nonuniform polynomial time for complexity theory, especially the P ?=NP question.