Complexity and Partitions

Complexity and Partitions

Loading...

##### Date

2001

##### Authors

##### Editors

##### Journal ISSN

##### Electronic ISSN

##### ISBN

##### Bibliographical data

##### Publisher

##### Series

##### URI (citable link)

##### International patent number

##### Link to the license

##### EU project number

##### Project

##### Open Access publication

##### Collections

##### Title in another language

##### Publication type

Dissertation of another university

##### Publication status

Published

##### Published in

##### Abstract

Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of classification problems for relations. For instance, a binary relation R typically defines a partitioning of the set of all pairs (x,y) into four parts, classifiable according to the cases where R(x,y) and R(y,x) hold, only R(x,y) or only R(y,x) holds or even neither R(x,y) nor R(y,x) is true. By means of concrete classification problems such as Graph Embedding or Entailment (for propositional logic), this thesis systematically develops tools, in shape of the boolean hierarchy of NP-partitions and its refinements, for the qualitative analysis of the complexity of partitions generated by NP-relations. The Boolean hierarchy of NP-partitions is introduced as a generalization of the well-known and well-studied Boolean hierarchy (of sets) over NP. Whereas the latter hierarchy has a very simple structure, the situation is much more complicated for the case of partitions into at least three parts. To get an idea of this hierarchy, alternative descriptions of the partition classes are given in terms of finite, labeled lattices. Based on these characterizations the Embedding Conjecture is established providing the complete information on the structure of the hierarchy. This conjecture is supported by several results. A natural extension of the Boolean hierarchy of NP-partitions emerges from the lattice-characterization of its classes by considering partition classes generated by finite, labeled posets. It turns out that all significant ideas translate from the case of lattices. The induced refined Boolean hierarchy of NP-partitions enables us more accuratly capturing the complexity of certain relations (such as Graph Embedding) and a description of projectively closed partition classes.

##### Summary in another language

##### Subject (DDC)

004 Computer Science

##### Keywords

Boolean hierarchy; NP; Theoretical computer science; computational complexity; lattices; partitions; posets

##### Conference

##### Review

undefined / . - undefined, undefined. - (undefined; undefined)

##### Cite This

## ISO 690

KOSUB, Sven, 2001.*Complexity and Partitions*[Dissertation]. WÃ¼rzburg: UniversitÃ¤t WÃ¼rzburg

## BibTex

@phdthesis{Kosub2001Compl-55844, year={2001}, title={Complexity and Partitions}, address={WÃ¼rzburg}, school={UniversitÃ¤t WÃ¼rzburg}, author={Kosub, Sven} }

## 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/55844"> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55844/3/Kosub_2-dd9hqkcgbjxw9.pdf"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T15:40:24Z</dcterms:available> <dc:contributor>Kosub, Sven</dc:contributor> <dc:creator>Kosub, Sven</dc:creator> <dc:rights>Attribution-NonCommercial-NoDerivatives 4.0 International</dc:rights> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T15:40:24Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:abstract xml:lang="eng">Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of classification problems for relations. For instance, a binary relation R typically defines a partitioning of the set of all pairs (x,y) into four parts, classifiable according to the cases where R(x,y) and R(y,x) hold, only R(x,y) or only R(y,x) holds or even neither R(x,y) nor R(y,x) is true. By means of concrete classification problems such as Graph Embedding or Entailment (for propositional logic), this thesis systematically develops tools, in shape of the boolean hierarchy of NP-partitions and its refinements, for the qualitative analysis of the complexity of partitions generated by NP-relations. The Boolean hierarchy of NP-partitions is introduced as a generalization of the well-known and well-studied Boolean hierarchy (of sets) over NP. Whereas the latter hierarchy has a very simple structure, the situation is much more complicated for the case of partitions into at least three parts. To get an idea of this hierarchy, alternative descriptions of the partition classes are given in terms of finite, labeled lattices. Based on these characterizations the Embedding Conjecture is established providing the complete information on the structure of the hierarchy. This conjecture is supported by several results. A natural extension of the Boolean hierarchy of NP-partitions emerges from the lattice-characterization of its classes by considering partition classes generated by finite, labeled posets. It turns out that all significant ideas translate from the case of lattices. The induced refined Boolean hierarchy of NP-partitions enables us more accuratly capturing the complexity of certain relations (such as Graph Embedding) and a description of projectively closed partition classes.</dcterms:abstract> <dcterms:issued>2001</dcterms:issued> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/4.0/"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/55844"/> <dcterms:title>Complexity and Partitions</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55844/3/Kosub_2-dd9hqkcgbjxw9.pdf"/> </rdf:Description> </rdf:RDF>

##### Internal note

##### xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

##### Examination date of dissertation

##### University note

WÃ¼rzburg, UniversitÃ¤t WÃ¼rzburg, Doctoral dissertation, 2001

##### Method of financing

##### Comment on publication

##### Alliance license

##### Corresponding Authors der Uni Konstanz vorhanden

##### International Co-Authors

##### Bibliography of Konstanz

No