Anzeige
Erschienen in:
06.07.2017
On the Complexity of Automatic Complexity
Erschienen in: Theory of Computing Systems | Ausgabe 4/2017
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Generalizing the notion of automatic complexity of individual words due to Shallit and Wang, we define the automatic complexity A(E) of an equivalence relation E on a finite set S of words. We prove that the problem of determining whether A(E) equals the number |E| of equivalence classes of E is NP-complete. The problem of determining whether A(E) = |E| + k for a fixed k ≥ 1 is complete for the second level of the Boolean hierarchy for NP, i.e., BH
2-complete. Let L be the language consisting of all words of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of L by showing that they can be co-context-free but not context-free, i.e., L is CFL-immune, but not coCFL-immune. We show that for each ε > 0, L
ε
∉ coCFL, where L
ε
is the set of all words whose deterministic automatic complexity A(x) satisfies A(x) ≥ |x|1/2−ε
.