On the complexity of automatic complexity

Abstract: Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity

A (E)

of an equivalence relation

E

on a finite set

S

of strings. We prove that the problem of determining whether

A (E)

equals the number

| E |

of equivalence classes of

E

is

m a t h s f N P

-complete. The problem of determining whether

A (E) = | E | + k

for a fixed

k g e 1

is complete for the second level of the Boolean hierarchy for

m a t h s f N P

, i.e.,

m a t h s f {B H}_{2}

-complete. Let

L

be the language consisting of all strings 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

m a t h s f C F L

-immune, but not

m a t h s f c o C F L

-immune. We show that for each

e p s i l o n > 0

,

L_{e} p s i l o n o t i n m a t h s f c o C F L

, where

L_{e} p s i l o n

is the set of all strings whose deterministic automatic complexity

A (x)

satisfies

A (x) g e | x |^{1 / 2 - e p s i l o n}

.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: On the complexity of automatic complexity