Relativized worlds with an infinite hierarchy
We introduce the "Book Trick" as a method for using results about random oracles to create relativized worlds with an infinite polynomial-time hierarchy. We use it to show, for example, a single relativized world where one can find satisfying assignments to satisfiable formulae with only nonadaptive queries to an NP oracle, and the counting class SPP strictly contains the polynomial-time hierarchy, and the polynomial-time hierarchy is infinite. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
relativization polynomial-time hierarchy theory of computation computational complexity ronald book