4.7 Random Oracles

Consider the class c04-math-0835 of all subsets of c04-math-0836 and define subclasses c04-math-0837 and c04-math-0838. One of the approaches to study the relativized c04-math-0839 question is to compare the two subclasses c04-math-0840 and c04-math-0841 to see which one is larger. In this subsection, we give a brief introduction to this study based on the probability theory on the space c04-math-0842.

To define the notion of probability on the space c04-math-0843, it is most convenient to identify each element c04-math-0844 with its characteristic sequence (i.e., the kth bit of αX is 1 if and only if ...

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.