The Boolean Hierarchy of NP-Partitions

Kosub, Sven; Wagner, Klaus W.

The Boolean Hierarchy of NP-Partitions

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2000

Autor:innen

Kosub, Sven

Wagner, Klaus W.

DOI (zitierfähiger Link)

https://doi.org/10.1007/3-540-46541-3_13

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

REICHEL, Horst, ed., Sophie TISON, ed.. STACS 2000 : 17th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Berlin: Springer, 2000, pp. 157-168. Lecture Notes in Computer Science. 1770. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-67141-1. Available under: doi: 10.1007/3-540-46541-3_13

Zusammenfassung

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 establish the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results.

Fachgebiet (DDC)

004 Informatik

Konferenz

Annual Symposium on Theoretical Aspects of Computer Science : STACS 2000, 17. Feb. 2000 - 19. Feb. 2000, Lille, France

Zitieren

ISO 690

KOSUB, Sven, Klaus W. WAGNER, 2000. The Boolean Hierarchy of NP-Partitions. Annual Symposium on Theoretical Aspects of Computer Science : STACS 2000. Lille, France, 17. Feb. 2000 - 19. Feb. 2000. In: REICHEL, Horst, ed., Sophie TISON, ed.. STACS 2000 : 17th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Berlin: Springer, 2000, pp. 157-168. Lecture Notes in Computer Science. 1770. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-67141-1. Available under: doi: 10.1007/3-540-46541-3_13

BibTex

@inproceedings{Kosub2000-03-24Boole-44989,
  year={2000},
  doi={10.1007/3-540-46541-3_13},
  title={The Boolean Hierarchy of NP-Partitions},
  number={1770},
  isbn={978-3-540-67141-1},
  issn={0302-9743},
  publisher={Springer},
  address={Berlin},
  series={Lecture Notes in Computer Science},
  booktitle={STACS 2000 : 17th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings},
  pages={157--168},
  editor={Reichel, Horst and Tison, Sophie},
  author={Kosub, Sven and Wagner, Klaus W.}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44989">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Wagner, Klaus W.</dc:contributor>
    <dc:contributor>Kosub, Sven</dc:contributor>
    <dc:creator>Kosub, Sven</dc:creator>
    <dcterms:title>The Boolean Hierarchy of NP-Partitions</dcterms:title>
    <dc:language>eng</dc:language>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">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 establish the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results.</dcterms:abstract>
    <dcterms:issued>2000-03-24</dcterms:issued>
    <dc:creator>Wagner, Klaus W.</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-12T12:13:43Z</dcterms:available>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-12T12:13:43Z</dc:date>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44989"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Nein