Minicomplexity

Abstract

The term minicomplexity was first suggested in [2], as a name for the field of theory of computation which studies the size complexity of two-way finite automata, as outlined in [1]. In this talk, we discuss the motivation behind this field and enumerate some of its prominent results in their historical context. By reformulating these results, we then attempt to reveal additional structure which often passes unnoticed. The present report records the start of this attempt.

1 Machines vs. Machines

Central in [1] is the invitation to start viewing the results in this field similarly to how results are being viewed in standard complexity theory: not as statements about the relative power of various computational devices, but as statements about the relative difficulty of various computational problems.

To describe the difference between the two viewpoints and stress the benefits of such a shift, we go back to the seminal paper of Meyer and Fischer [5], which initiated the field, and to the three very first propositions in it. The first one$^{(1)}$

says that one-way nondeterministic finite automata () are strictly more powerful than deterministic ones (), as some binary witness language $R_n$ needs ${\le } n$ states on but ${\ge }2^n$ states on . In the proof, $R_n$ is described only through its deciding . After it, one more witness $R_n'$ is given:

which is (suboptimal, but) simpler, together with its restriction $R_n''$ (our name) to strings of length ${<}2n$, which shares the same properties.$^{(2)}$ The next proposition

establishes a similar relation for two-way deterministic finite automata () and : now a witness language $F_n$ needs O(n) states on but ${\ge } n^n$ states on . Finally, the third proposition

proves that, augmented with a pebble,  are even more powerful: O(n) states are now enough to decide a language $P_n$ for which need ${\ge } 2^{2^n}$ states. In short, and in the standard parlance of the field, Propositions 1–3 tell us that the trade-off in the conversion from , , or single-pebble to is respectively $2^{\varOmega (n)}, 2^{\varOmega (n\lg n)}$, and $2^{2^{\varOmega (n)}}$.

Overall, this is entirely a “machines vs. machines” discussion: computational devices compete against each other, and we want to know which is more powerful. In this competition, problems play only the secondary role of a witness task on which a stronger machine beats a weaker one by solving it with less resources.

2 Problems vs. Problems

The alternate viewpoint is “problems vs. problems”: computational tasks compete against each other, and we want to know which is more difficult. This time it is machines that play the secondary role, of a witness device on which a harder problem beats an easier one by requiring more resources.

This is the viewpoint of standard complexity theory, and it was proposed for minicomplexity, as well, by Sakoda and Sipser in their own seminal paper [6]. By switching to this viewpoint, we bring problems at the center of attention: we clearly describe them as computational tasks (as opposed to sets of strings); give them distinctive names; and collect them in complexity classes relative to the various machines and the polynomiality or not (as opposed to the asymptotics) of the used resources. For practical reasons, we also use h as the important parameter (instead of n, which is often needed as input length); and describe the instances over a large alphabet and with an associated promise for the format (if this simplifies the description without affecting the difficulty).

2.1 RETROCOUNT

For example, $R_h'$ (Proposition 1) is the problem: “Given a bitstring, check that its h-th from the last digit is .” Note that the reference “h-th from the last digit” is void on strings of length ${<}h$. We could get into a discussion of whether such strings should be accepted or not, but this would be a distraction from the main point of the task. A better description of the essence of this computational problem is one where the intended format of the input is taken for granted:

(1)

so that a solving machine need not check that the length is ${\ge } h$; if it is not, then the machine is free to decide arbitrarily. We call this problem . Similarly, the restriction $R''_h$ is the problem :

(2)

Again, it is not the job of a solving machine to check that the length of the input is appropriate; this is promised. The job is only to check the h-th last bit.

Formally, a (promise) problem $\mathfrak {L}$ over an alphabet $\varSigma$ is a pair $(L,\tilde{L})$ of disjoint subsets of $\varSigma ^*$. A string w is an instance of $\mathfrak {L}$ if $w\in L\cup \tilde{L}$, and is positive, if $w\in L$, or negative, if $w\in \tilde{L}$. To solve $\mathfrak {L}$ is to accept all $w\in L$ but no $w\in \tilde{L}$ (behaving arbitrarily on $w\not \in L\cup \tilde{L}$). So, (1) and (2) are the promise problems

That both problems witness the exponential difference in number of states between and is expressed by the fact that both belong to the class

(3)

of “problems solved by small ”, but not in the respective class  for :

(4)

where is the induced family, and similarly for . Note that, since the latter problem is a restriction of the former, all the information of (4) follows from the next two facts and lemma.

Fact 1

.

Fact 2

.

Lemma 1

If $\mathcal {L}\subseteq \mathcal {L}'$ and , then .

Here, $\mathcal {L}\subseteq \mathcal {L}'$ means that the family $\mathcal {L}\,{=}\,(\mathfrak {L}_h)_{h\ge 1}$ is a restriction of $\mathcal {L}'=(\mathfrak {L}'_h)_{h\ge 1}$ (so that ); equivalently, we also say that $\mathcal {L}'$ is a generalization of $\mathcal {L}$. Formally, for $\mathfrak {L}\,{=}\,(L,\tilde{L})$ and $\mathfrak {L}'=(L',\tilde{L}')$, we write $\mathfrak {L}\subseteq \mathfrak {L}'$ if both $L\subseteq L'$ and $\tilde{L}\subseteq \tilde{L}'$; then we write $\mathcal {L}\subseteq \mathcal {L}'$ if $\mathfrak {L}_h\subseteq \mathfrak {L}'_h$ for all h.

2.2 PROJECTION

For another example, $F_h$ (Proposition 2) is the problem: “Given a string, check that it consists of a tuple of h numbers from 1 to h (in unary, by s; delimited by s), an index k from 1 to h (in unary, by s), and the k-th number in the tuple (in unary, by s).” Clearly, the essence of this task is to check that the number after k equals the k-th number in the tuple. So, a better description is:

(5)

so that, as above, checking that the input is correctly formatted is not important.

Also unimportant is the fact that the numbers and index are in unary. The problem preserves its essence, if we assume that the input cells are large enough to host any number from $[h]:=\{1,\dots ,h\}$. So, an even better description of $F_h$ is

(6)

where the input alphabet is [h]. Now it is more clear what the problem is: to check that the projection of the given tuple to its k-th component returns i. So, we refer to (6) as ;$^{(3)}$ and use for (5).

With these clarifications, Proposition 2 says that , where the class of “problems solved by small ” is defined similarly to (3). Intuitively, the reasons for this fact are clear: When a solving  crosses the boundary between the tuple and the index, it must be able to answer any query of the form “does the k-th component equal i?”, so it must store the full tuple, which needs ${\ge } h^h$ states. In contrast, a can read and store k and i; rewind; then countdown to the k-th block of s to check that it contains exactly i of them, all doable with $O(h^2)$ states. Similarly, .

Now that we see why these problems witness , we may further ask: Do we really need the tuple numbers in separate cells? Or k and i in separate cells? No. Over the alphabet $[h]^h\cup [h]^2$, where cells are large enough to host an entire h-tuple $\overline{i}$ or query $u=(k,i)$, we may define the problem :

(7)

Intuitively, this is the best description of the essence of $F_h$, as it contains exactly the structure that is sufficient and necessary to place it in .

Of course, problems (5), (6), and (7) are “essentially the same”. To describe this intuition formally, we first define them as promise problems. E.g., (7) is:

and similarly for (5) and (6), over alphabets and [h]. We then introduce reductions, as follows. For arbitrary problems $\mathfrak {L}=(L,\tilde{L})$ and $\mathfrak {L}'=(L',\tilde{L}')$ over alphabets $\varSigma$ and $\varSigma '$, we say that $\mathfrak {L}$ to $\mathfrak {L}'$ () if there exists a one-way deterministic finite transducer () T such that

$$\begin{aligned} w\in L\implies T(w)\in L' \qquad \text {and}\qquad w\in \tilde{L}\implies T(w)\in \tilde{L}' \end{aligned}$$

(8)

where T(w) is the output of T on input w, if T accepts w, or undefined, otherwise. An alternative and more concise way to write (8) is:

$$\begin{aligned} T(\mathfrak {L})\subseteq \mathfrak {L}' \end{aligned}$$

(9)

where $T(\mathfrak {L})=T(L,\tilde{L})=(T(L),T(\tilde{L}))=\bigl (\,\{T(w)\,{\mid }\,w\in L\},\{T(w)\,{\mid }\,w\in \tilde{L}\}\,\bigr )$ is the pair of the images under T of all positive and all negative instances of $\mathfrak {L}$ (which is itself a problem iff $T(L)\cap T(\tilde{L})\ne \emptyset$). As further alternative,

(10)

says the same, without identifying T (i.e., it is equivalent to ).

In the special case where the inclusion (9) is an equality, $\mathfrak {L}'$ is a -image of $\mathfrak {L}$ under T, and we also write (10) as equality. E.g., (5) is a -image of (6):

(11)

via the O(h)-state  T which scans an instance $i_1i_2\dots i_h ki$ and, for each symbol in [h], prints the appropriate unary representation and delimiters. Note that T prints on its output tape only $h+2=\text {poly}(h)$ times; and, in each of these times, the printed string has length ${\le } h+1=\text {poly}(h)$.

In another special case, where T has only 1 state and always accepts, T defines a homomorphism $H:\varSigma \cup \{{\vdash }{,}{\dashv }\}\rightarrow (\varSigma ')^*$ such that $T(w)=H({\vdash }w{\dashv })$. We then say that $\mathfrak {L}$ homomorphically reduces to $\mathfrak {L}'$ ( or ), if $H(\mathfrak {L})\subseteq \mathfrak {L}'$; or that $\mathfrak {L}'$ is a homomorphic image of $\mathfrak {L}$ (), if $H(\mathfrak {L})=\mathfrak {L}'$. Hence,

(12)

via the homomorphism H which maps every h-tuple $\overline{i}=(i_1,i_2,\dots ,i_h)$ to the string $i_1i_2\cdots i_h$, every query $u=(k,i)$ to the string ki, and each of ${\vdash }{,}{\dashv }$ to $\epsilon$. Note that H maps every symbol to a string of length ${\le } h=\text {poly}(h)$.

These definitions extend to problem families $\mathcal {L}=(\mathfrak {L}_h)_{h\ge 1}$ and $\mathcal {L}'=(\mathfrak {L}'_h)_{h\ge 1}$, if every $\mathfrak {L}_h$ reduces to some $\mathfrak {L}'_{h'}$ via a  $T_h$ or a homomorphism $H_h$. However, to say that , , , or , we also need $h'$ and the size of $T_h$ to be small relative to h: namely, that $h'=\text {poly}(h)$ and $T_h$ has $\text {poly}(h)$ states. If, in addition, every $T_h$ prints only $\text {poly}(h)$ times, then we write and call the $T_h$ laconic; if every printed string has length only $\text {poly}(h)$, then we write (or ) and call the $T_h$ (or $H_h$) tight. Hence,

(13)

by the tight laconic transducers of (11) and the tight homomorphisms of (12).

In conclusion, (13) expresses the intuition that problems (5), (6), and (7) are “essentially the same”. Now, the fact that they all witness  follows from only two easy facts and standard lemmas [6, Sect. 3], [4, Corollary 3]:

Fact 3

.

Fact 4

.

Lemma 2

 is closed under and .

Lemma 3

 is closed under (and thus also under and ).

2.3 MEMBERSHIP

Let us now return to Proposition 1 and see how large alphabets can help us better understand the essense of its problems, too.

In , every instance w is of the form uv, where $|u|=h$ and $0\le |v|<h$. Note that the actual bits of v are unimportant; only $l\,{:=}\,|v|$ matters: w is positive iff the $(l+1)$-st bit of u is . Namely, if $\alpha \subseteq [h]$ is the set of the indices of all ’s in u, then w is asking whether $l+1\in \alpha$. So, the question is really whether a set $\alpha$ contains an element i; it’s just that $\alpha$ is given in binary (by its characteristic vector u) and i is given in unary (by the length $i-1$ of v).

Let us also recall why . On crossing the u-v boundary, a solving must be able to handle any l, i.e., any query of the form “does the i-th bit of u equal ?”; so it must store the full u, which needs ${\ge }2^h$ states. In contrast, a can scan u; guess the crucial ; countdown from h on the next bits (entering v at count i, for i the index of the guessed ); and accept iff the count is 1 on ${\dashv }$ (so $|v|=i-1$), all doable with O(h) states.

Now that we better understand what the problem is asking and why it is a witness, we may ask: Do we really need $\alpha$ in binary and i in unary? No. Over the alphabet $\{\alpha \mid \alpha \subseteq [h]\}\cup [h]$, we define the problem: “Given a set $\alpha \subseteq [h]$ and an element $i\in [h]$, check that $i\in \alpha$”, or formally:$^{(4)}$

(14)

and claim that this best captures the essence of . That the two problems are “essentially the same” is formally expressed by the fact that the former homomorphically reduces to the latter via the obvious homomorphism which maps every $\alpha$ to its characteristic vector and every i to :

(15)

What about ? Its instances are derived by left-padding those of by arbitrary bitstrings. Formally, let $\textsf {\small LPAD}$ be the operator which maps $\mathfrak {L}=(L,\tilde{L})$ to the pair . This pair is not necessarily a promise problem: if there exist instances $w\in L$ and $\tilde{w}\in \tilde{L}$ and pad-strings such that $xw=\tilde{x}\tilde{w}$, then the two sets in the pair are not disjoint. So, call $\mathfrak {L}$ left-paddable, if this does not happen. Then a family $\mathcal {L}=(\mathfrak {L}_h)_{h\ge 1}$ is left-paddable if every $\mathfrak {L}_h$ is; and $\textsf {\small LPAD} (\mathcal {L}):=(\textsf {\small LPAD} (\mathfrak {L}_h))_{h\ge 1}$.

Easily, is left-paddable, since the sign of each instance is determined by its last h bits and these are unaffected by the padding; and

(16)

Overall, (15) and (16) formally relate (1), (2), and (14) to each other. Now, the fact that all three witness follows from only two easy facts and from suitable lemmas (Lemma 1, as $\mathcal {L}\subseteq \textsf {\small LPAD} (\mathcal {L})$; Lemma 3; and Lemmas 4–5):

Fact 5

.

Fact 6

.

Lemma 4

 is closed under .

Lemma 5

If $\mathcal {L}$ is left-paddable and , then .

Note how our earlier Facts 1 and 2 now become corollaries of Facts 5 and 6.

Retrocount vs. Projection. There is great similarity between our intuition why the projection problems are not in  and why the same holds for the retrocount problems. This suggests that the projection problems also have at their core. Indeed:

(17)

by the homomorphism which maps every set $\alpha \subseteq [h]$ to its “characteristic tuple” $\overline{i}\in [h+1]^{h+1}$ where $i_j=1$ or $h+1$, based on whether $j\in \alpha$ or not, respectively; and each $i\in [h]$ to the query (i, 1).$^{(5)}$ So, our earlier Fact 4 is now a corollary of Fact 6 (via (17) and Lemma 3). At the same time,  is also a witness of , because Fact 3 implies it is in  (via (13), (17), and Lemma 2).

2.4 LIST MEMBERSHIP

We now continue to problem $P_h$ (Proposition 3): “Given a string, check that it is a strictly increasing list of h-long binary numbers (delimited by s), followed by a copy of one of them (separated by ).” Clearly, the essence of this task is to check that the number after  appears in the preceding list. The condition that the list is strictly increasing is there to ensure that $P_h$ is finite. Ignoring it (also dropping the finiteness of $P_h$ from Proposition 3), we arrive at this better description:

(18)

As previously, presenting the numbers in binary is unimportant; all that matters is that each block of h bits can host $2^h$ different strings. It is important, however, to know when we have arrived at i. So, to zoom into the essence of $P_h$, we switch to alphabet $[2^h]\cup \{\check{\imath }\mid i\in [2^h]\}$, where each cell hosts a full number x (possibly ticked, as $\check{x}$) in $[2^h]$ (as opposed to $\{0,\dots ,2^h-1\})$, and define the problem:

(19)

In it, one easily sees a variant of , where elements are drawn (not from [h], but) from $[2^h]$; and the set is given (not in a single cell, but) as a list over many cells, possibly with repetitions. To represent this problem, we first introduce its variant over the smaller alphabet [h]:$^{(6)}$

(20)

and refer to (19) itself, over $[2^h]$, as . Then, for (18) we use the name .

So, Proposition 3 says that , where and are the classes for small single-pebble and large , where “large” means “with $2^{\text {poly}(h)}$ states”. Once again, the intuitive reasons are clear: on crossing , a solving  must have stored the set of numbers occurring in the list, which needs ${\ge }\smash {2^{2^h}}$ states. In contrast, a single-pebble can compare i against every $i_j$ bit-by-bit, using the pebble to mark the current $i_j$, all doable with O(h) states. By the same reasons, . (Note that it is important for the pebble to have the list spread across cells.)

Note that our intuition for the lower bound is the same as for , except now there are exponentially more sets to remember. To represent this formally, let us first note that

(21)

via the homomorphism which maps every set $\alpha \subseteq [h]$ to a string $i_1i_2\cdots i_t$ of its members; and every $i\in [h]$ to its ticked variant $\check{\imath }$. We then also note that (19) can be obtained from by applying an operator TALL,

(22)

which maps a family $\mathcal {L}=(\mathfrak {L}_h)_{h\ge 1}$ to its sub-family $\textsf {\small TALL} (\mathcal {L})=(\mathfrak {L}_{2^h})_{h\ge 1}$ at indices which are powers of 2; and (18) can be obtained from (19) homomorphically

(23)

by mapping every $i\in [2^h]$ to the h-long binary representation of $i-1$, preceded or followed by 2, depending on whether i is ticked or not. Now, the lower bound of Proposition 3 follows from (21), (22), and (23) and a strengthening of Fact 6.

To see how, we start with some definitions and facts. The class corresponds to with quasi-polynomially many states (i.e., $2^{\text {poly}(\log n)}$ states). We can easily show the next strengthening of Fact 6 (by the standard reasoning, that needs ${\ge }2^h$ states on a ) and variation of Lemma 3:

Fact 7

.

Lemma 6

and are closed under .

A family $\mathcal {L}=(\mathfrak {L}_h)_{h\ge 1}$ is self-homomorphic if for all $h\le h'$; intuitively, if the instances of every $\mathfrak {L}_h$ can be seen as instances of every higher $\mathfrak {L}_{h'}$. Easily, is self-homomorphic, and we can prove that:

Lemma 7

If $\mathcal {L}$ is self-homomorphic and , then .

Now, we can apply the following reasoning:

Overall, we see that the lower bound of Proposition 3 follows from the hardness of the core problem of Proposition 1 (Fact 7) and from properties of the classes.

For the upper bound of Proposition 3, we see that one of the two witnesses satisfies it because the other one does: follows from the next fact and lemma, and since the homomorphisms of (23) are tight:

Fact 8

.

Lemma 8

is closed under .

3 Modular Witnesses

The three propositions of [5] offered witness languages for the differences , , and . By analyzing these languages, we arrived at eight promise problems witnessing these differences. In the end, all bounds that we needed for these problems followed from Facts 3, 5, 8 (for the upper bounds) and Fact 7 (for the lower bounds), via the established relations between these problems and using a collection of lemmas of three distinct types:

• preservation of hardness: These are lemmas of the form

  

  where $\mathcal {L}'$ is derived from $\mathcal {L}$. E.g., Lemma 1 is such a lemma, with $\mathcal {L}'$ any generalization of $\mathcal {L}$. Similarly for every lemma for the closure of a class under or , with $\mathcal {L}'$ any generalization of  or .

• propagation of hardness: These are lemmas of the form

  

  where  are derived from  [3]. E.g., Lemma 7 is such a lemma, where $\mathcal {L}'\,{=}\,\textsf {\small TALL} (\mathcal {L})$, and is derived from  by an application of the general operator which raises the size bound f(h) of a class to $f(2^h)$.

• preservation of easiness: These are lemmas of the form

  

  where $\mathcal {L}'$ is derived from $\mathcal {L}$. E.g., Lemma 5 is such, with $\mathcal {L}'=\textsf {\small LPAD} (\mathcal {L})$ and . Same for any lemma for the closure of a class under an operation.

Hence, the propositions of [5] are connected via structural relations between their witnesses, which are easy to miss if we do not adopt the right point of view.

We now further observe that the relations between witnesses allow us to express each of them as a generalization of a problem that can be obtained from by applying a sequence of operators. Specifically, in the following list, every witness on the left generalizes the problem on the right:

where $\mathcal {H}_{15}$ is the family of the homomorphic reductions that justifies (15), and similarly for all other $\mathcal {H}_i$ and $\mathcal {T}_i$. Every lower bound for a witness on the left was established by proving a lower bound for the corresponding problem on the right and then using Lemma 1. Again by (the contrapositive of) Lemma 1, every upper bound for a witness on the left is also an upper bound for the respective problem on the right. Overall, the problems on the right witness the same differences as the problems on the left.

Let a modular witness for a difference be any problem which belongs to the difference and is derived from by applying a sequence of operators. Our discussion above shows that every one of the differences in Propositions 1–3 of [5] admits a modular witness.

We conjecture that the same is true for all differences in minicomplexity. Namely that, for every two minicomplexity classes and :

In the talk, we will examine as evidence supporting this conjecture several examples of known separations where the offered witnesses were indeed (generalizations of) modular ones or can be replaced by modular witnesses.

If this conjecture is true, then designing a witness for a separation reduces to (i) deciding which sequence of operators to apply to , and then (ii) proving the corresponding necessary lemmas of hardness propagation and of hardness or easiness preservation. Gradually, this could lead to a library of operators and corresponding lemmas, available for reuse in (i) and (ii). It would, of course, also be interesting to see a proof of the conjecture, that explains why is sufficient as the only “seed of hardness” in this domain.

If the conjecture is false, it would be interesting to see examples where it fails. Understanding these examples, one could then suggest conditions under which the conjecture remains valid, and work with this updated, restricted variant.

Notes

• (1) Proposition 1 also includes a last sentence, that the reverse of $R_n$ needs only O(n) states on a . We omitted that sentence, as it is redundant for our purposes.

• (2) We write “${<}2n$”, although the definition of $R''_n$ also allows strings of length exactly 2n. Excluding such strings does not change the desired properties of $R''_n$ in the context of Proposition 1; and is convenient for our purposes.

• (3) In [2], the name was used for the reverse of this problem.

• (4) In [2], the name was used for the reverse of this problem.

• (5) Note the redundant component $i_{h+1}$, which is always set of $h+1$. We need $h+1$ components, because we need $h+1$ values; and we need $h+1$ values, because we need to ensure that the max and min values are distinct even when $h=1$.

• (6) In [2], the reverse of this problem was called $\exists$ equality.