Complexity and Partitions

Cite This

Files in this item

Checksum: MD5:6cf1acc7440a260eb6a6a522cec4a315

KOSUB, Sven, 2001. Complexity and Partitions [Dissertation]. Würzburg: Universität Würzburg

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

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dcterms:isPartOf rdf:resource=""/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="">2021-12-10T15:40:24Z</dc:date> <dc:rights>Attribution-NonCommercial-NoDerivatives 4.0 International</dc:rights> <dspace:isPartOfCollection rdf:resource=""/> <dspace:hasBitstream rdf:resource=""/> <dcterms:issued>2001</dcterms:issued> <dcterms:rights rdf:resource=""/> <dcterms:hasPart rdf:resource=""/> <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:title>Complexity and Partitions</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Kosub, Sven</dc:contributor> <dcterms:available rdf:datatype="">2021-12-10T15:40:24Z</dcterms:available> <dc:language>eng</dc:language> <dc:creator>Kosub, Sven</dc:creator> <bibo:uri rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Dec 10, 2021 (Information about access statistics)

Kosub_2-dd9hqkcgbjxw9.pdf 42

This item appears in the following Collection(s)

Attribution-NonCommercial-NoDerivatives 4.0 International Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivatives 4.0 International

Search KOPS


My Account