Login
- Document type:
- Technical Report
- Author(s):
- Sven Kosub; Klaus W. Wagner
- Title:
- The Boolean Hierarchy of NP-Partitions
- 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.
- Keywords:
- computational complexity theory; classification problems; entailment; partitions; boolean hierarchy; polynomial hierarchy; completeness; orders; lattices
- Year:
- 2002
- Year / month:
- 2002-08-01 00:00:00
- Pages:
- 50
BibTeX