Structured Concepts in Relativised Hierarchies
Leen Torenvliet

Abstract:
In this thesis we show by construction of oracle sets that a strong separation of complexity classes in the lower levels of the Polynomial Time Hierarchy is possible.

In chapter I we develop a model for the interpretation of the constructions in subsequent chapters in an informal but precise way, and we develop precisely that part of computational complexity theory needed to understand the notions used in these chapters.

In chapter II we (partially) quote existing theory, and prove one new theorem. We show in this chapter the constructions which would give to oracle set A the following properties respectively: NP(A) ≠ P(A), NP(A) ≠ Co- NP(A), NP(A) has a P(A)-immune set, NP(A) has a simple set (with two different constructions), and NP(A) has a single set which is both simple and P(A) immune.

In chapter III we treat the separation results between the first and second level of the hierarchy. We limit ourselves in this chapter to strong separations. We show the constructions which would give to oracle set A the following properties respectively: \Sigma^P_2(A) has an NP(A) immune set, \Pi^P_2(A) has an NP(A) immune set, \Sigma^P_2(A) has an NP(A) bi-immune set, \Sigma^P_2(A) has an \Delta^P_2(A) immune set, and \Pi^P_2 has an \Delta^P_2(A) immune set.

In chapter IV we treat the construction of an oracle set A such that \Sigma^P_2(A) has a simple set, and thus obtain a strong separation between \Sigma^P_2(A) and \Pi^P_2(A) on the second level of the hierarchy.