|Abstract of Paper|
On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
by Sven Kosub
The boolean hierarchy of $k$-partitions over NP for $k$ at least 2 was introduced as a generalization of the well-known boolean hierarchy of sets. The classes of this hierarchy are exactly those classes of NP-partitions which are generated by finite labeled lattices. We extend the boolean hierarchy of NP-partitions by considering partition classes which are generated by finite labeled posets. Since we cannot prove it absolutely, we collect evidence for this extended boolean hierarchy to be strict. We give an exhaustive answer to the question which relativizable inclusions between partition classes can occur depending on the relation between their defining posets. The study of the extended boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the extended boolean hierarchy of $k$-partitions over NP is strict, we give a complete characterization when such solution reductions are possible. This contributes to an open problem raised by Hemaspaandra, Ogihara, and Wechsung.