The boolean hierarchy of NP-partitions

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

KOSUB, Sven, Klaus W. WAGNER, 2008. The boolean hierarchy of NP-partitions. In: Information and Computation. 206(5), pp. 538-568

@article{Kosub2008boole-3019, title={The boolean hierarchy of NP-partitions}, year={2008}, doi={10.1016/j.ic.2007.06.003}, number={5}, volume={206}, journal={Information and Computation}, pages={538--568}, author={Kosub, Sven and Wagner, Klaus W.} }

We introduce the boolean hierarchy of k-partitions over NP for k>=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>=3 turns out to be much more complicated. We formulate the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results. Publ. in: Information and Computation, 206 (2008), 5, pp. 538-568 Kosub, Sven Wagner, Klaus W. eng 2011-03-23T10:15:48Z deposit-license Kosub, Sven 2011-03-23T10:15:48Z The boolean hierarchy of NP-partitions Wagner, Klaus W. 2008

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto