Advertisement
Published in:
06-07-2017
On the Complexity of Automatic Complexity
Published in: Theory of Computing Systems | Issue 4/2017
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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−ε
.