Benutzer: Gast  Login
Titel:

The Boolean Hierarchy of NP-Partitions

Dokumenttyp:
Technical Report
Autor(en):
Sven Kosub; Klaus W. Wagner
Abstract:
We introduce the boolean hierarchy of k-partitions over NP for k at least 3 as a generalization of the boolean hierarchy of sets (i.e., 2-partitions) over NP. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy of k-partitions over NP for k at least 3 turns out to be much more complicated. We establish the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results.
Stichworte:
computational complexity theory; classification problems; entailment; partitions; boolean hierarchy; polynomial hierarchy; completeness; orders; lattices
Jahr:
2002
Jahr / Monat:
2002-08-01 00:00:00
Seiten/Umfang:
50
 BibTeX