Forcing and genericity on the polynomial hierarchy
James A. Foster · 1990
The main project of this thesis is to lay the theoretical groundwork for using forcing to explore the polynomial hierarchy. The approach is to generalize previous restrictions of set theoretic forcing to be applicable to structures constructed from alternating bounded quantifiers. First, the paper reviews the history of forcing and genericity as techniques for studying computability and complexity. This thesis then defines forcing and genericity for PH both syntactically and constructively. The two approaches are then shown to be equivalent. In particular, the quantifier bound does not have to be stated in the syntactic approach, since it is hidden in the underlying language. This allows many classical proofs to be directly applied in the bounded case. Restricted forcing is next proven monotonic, consistent and quasicomplete, and forcing is proven equivalent to satisfaction. Furthermore, restricted generic sets with arbitrary prefixes are proven to exist, even when the restrictions are relaxed to arbitrary classes of recursively enumerable sets and functions. This paper examines the computational complexity of restricted generic sets for arbitrary levels of PH. It proves an upper bound of deterministic time $O(2\sp{2{\sp n}})$ on generic sets for any level of PH, even when the generic construction proceeds with a very powerful lookahead. In the other direction, constructions with fixed lookahead yield generic sets decidable deterministically in time $O(2\sp{n{\sp c}}$) for some constant $c$. The paper proves that a set generic for a level of PH is strong nondeterministically turing reducible to any universal set for that level. Finally, previous results about classes of generic sets are adapted to sets generic for levels of PH. In particular, the class of sets generic for higher levels is included in the class for lower levels, and increasing the lookahead so as to dominate finite iterations reduces the size of the class. This yields a new approach to the P versus NP problem: investigate inclusion properties of classes of restricted generic sets.