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