Complexity and Automata

Computational Complexity: NP-complete Sets

Notably, all known NP-complete sets are isomorphic. This means that for such sets A and B there exists a polynomial-time-computable and polynomial-time-invertible bijection f such that x belongs to A if and only if f(x) belongs to B. So up to isomorphism, the known NP-complete sets are one and the same set.

So far one cannot prove this for all NP-complete sets. Therefore, researchers are interested in weaker properties that provably hold for all NP-complete sets. For instance, one can show that all infinite NP-complete sets can be split into an arbitrary number of NP-complete sets. Hence all these sets share a certain degree of redundancy. The aim of current research is to find further such properties that can be proved for all NP-complete sets.

 

Theory of Automata and Formal Languages: Dot-Depth Problem

Regular languages can be described by regular expressions. They consist of single letters and the operations union, concatenation, and iteration. We can additionally admit intersection and complementation without leaving the class of regular languages. If we abstain from iteration, this leads to starfree regular expressions, which describe starfree regular languages.

The dot-depth problem asks to find a starfree regular expression with a minimal number of nested concatenations and complements that describes a given starfree regular language. Up to now it is open whether or not this problem can be solved algorithmically. In order to approach this very difficult problem, the current research concentrates on solving the dot-depth problem for subclasses of starfree regular languages.

 

Contact: Christian Glaßer