Abstract of Paper

On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
by Sven Kosub

Abstract:

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.