2003 | OriginalPaper | Buchkapitel
Boolean NP-Partitions and Projective Closure
verfasst von : Sven Kosub
Erschienen in: Discrete Mathematics and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
When studying complexity classes of partitions we often face the situation that different partition classes have the same component classes. The projective closures are the largest classes among these with respect to set inclusion. In this paper we investigate projective closures of classes of boolean NP-partitions, i.e., partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. We prove that the projective closures of these classes are represented by finite labeled posets. We give algorithms for calculating these posets and related problems. As a consequence we obtain representations of the set classes NP(m) ∩ coNP(m) by means of finite labeled posets.