4.7 Random Oracles
Consider the class 
of all subsets of 
and define subclasses 
and 
. One of the approaches to study the relativized 
question is to compare the two subclasses 
and 
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 
.
To define the notion of probability on the space 
, it is most convenient to identify each element 
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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
