Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style


Sven Kosub:

Complexity and Partitions

Institut für Informatik
Fakultät für Mathematik & Informatik
Julius-Maximilians-Universität Würzburg
Am Hubland, D-97074 Würzburg, Germany



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.

Table of contents:

  1. Introduction

  2. Preliminaries
    2.1 Mathematical Notions and Notations
    2.2 Complexity Classes and Hierarchies
    2.3 Partitions

  3. The Boolean Hierarchy of NP-Partitions
    3.1 Partition Classes Defined by Finite Functions
    3.2 Partition Classes Defined by Lattices
    3.3 Comparing Partition Classes
    3.4 Minimal Descriptions of Partition Classes
    3.5 The Embedding Conjecture
    3.6 On the Structure of BH3 (NP)
    3.7 Machines That Accept Partitions

  4. Refining the Boolean Hierarchy of NP-Partitions
    4.1 Partition Classes Defined by Posets
    4.2 An Alternative Approach
    4.3 Characterizing the Projective Closure
    4.4 A Relativized Embedding Theorem

  5. Some Applications
    5.1 Separability within NP
    5.2 Fine Hierarchies inside BH2 (NP)
    5.3 Reducing the Set of Solutions of NP Problems

Number of pages: 116

ISSN 1433-8092 | Imprint