5
$\begingroup$

This is a spinoff of my attempt to capture the notion of 'explicit bijection' at https://mathoverflow.net/a/323827.

I wonder whether it is possible to formalize the idea that an algorithm computing a map $f:A\to B$ between two finite sets does not 'know' or 'use' a description of $B$.

Let me give two examples to illustrate what I mean. Let $A$ be the set of binary words of length $n$.

For the first example, let $f$ be the map corresponding to the following algorithm:

  • let $w=w_1\dots w_n$ be the binary word
  • let $i=1$
  • for $l$ in $w$, reading the word left to right:
    • if $l=1$ increase $i$ by one
    • otherwise write down $i$, and set $i=1$
  • write down $i$.

That is, the word $1$ is mapped to $2$ and the word $0$ is mapped to $1,1$. In general, this algorithm associates (bijectively) to each binary word of length $n$ a composition of $n+1$. So $B$ is the set of integer compositions of $n+1$, but it seems (to me) that the algorithm does not use this fact.

For the second example, let $f$ be the map corresponding to the following algorithm:

  • let $w=w_1\dots w_n$ be the binary word
  • let $k=\sum_{i=1}^n 10^{(n-i)w_i}$
  • sort the integer compositions of $n+1$ into lexicographic order and write down the $k$-th.

It is not hard to see that the two maps coincide. However, I would (like to) say that the second algorithm uses the fact that $B$ is the set of integer compositions of $n+1$.

$\endgroup$
  • 1
    $\begingroup$ I assume that by $10$ you mean $1+1.$ $\endgroup$ – Aaron Meyerowitz Feb 25 at 21:56
  • $\begingroup$ Yes :-) It's binary, after all! $\endgroup$ – Martin Rubey Feb 25 at 21:59
  • $\begingroup$ The second algorithm has a black box where there is a (not yet sorted) list of integer compositions of $n+1$ that comes out of nowhere. If I were to pick such a listing for use in the second algorithm I would probably pick the natural one given by the first algorithm, but then the two algorithms are essentially the same (with just a bit of extra overhead in the second algorithm). To play the devil's advocate: how are the two algorithms significantly different? (Except that the second is a slight generalization of the first.) $\endgroup$ – François G. Dorais Feb 26 at 2:45
  • $\begingroup$ @FrançoisG.Dorais: yes, that is in fact my question! Here is another example, taken from mathoverflow.net/a/323827: Dyck paths of semilength $n$ with exactly one valley are in bijection with subsets of size $2$ in $\{1,\dots,n\}$. I would like to distinguish the algorithm that sorts the Dyck paths and the subsets and maps the Dyck path to the subset with the same index, from an algorithm that implements an 'explicit bijection', whatever that is. Note that in this case the two sets are rather small in terms of $n$, in contrast to the example with binary words. $\endgroup$ – Martin Rubey Feb 26 at 6:14
  • $\begingroup$ One proposal is to restrict the amount of working memory available as in @James answer. However, I wonder whether one can unambiguously define the idea that an algorithm "visits" many elements of $B$. $\endgroup$ – Martin Rubey Feb 26 at 6:42
1
$\begingroup$

I think regular (or close to regular) languages and finite state automatons might be relevant here.

A language is just a subset of the set of all strings over some alphabet. Classes of combinatorial objects can often be represented as languages with fairly nice descriptions.

A finite state automaton is basically a computer with a fixed, finite amount of memory. It can read from an input tape, but cannot write to it, and does not have an infinite "scratch work" tape. A language L is regular if there is a finite state automaton which halts if and only if the string on the input tape is in L.

We'll also extend this notion to function from one language to another. We'll say a function $f: L \rightarrow L'$ is automaton computable if it can be implemented by a computer with a fixed, finite amount of memory that can read from and navigate through the input tape, write to and navigate through the output tape, but cannot write to the input tape or read from the output tape.

An example here is if L is the set of all binary strings, and L' is the set of all binary strings of even length all of whose even digits are 0, then there is a automaton computable bijection from L to L' given by taking an input string $w_1w_2 \dots w_n$, reading it left to right, and writing $w_i0$ to the output tape for each letter $w_i$ we read.

If we slightly modify your first algorithm, I think it's right to say it is automaton computable. Language L will be the set of finite binary strings, and language L' will be the set of finite sequences of unary numbers, where a sequence of unary numbers is represented by $111...110111...110111...110111...11$, i.e. with a sequence of k 1s representing the number k, with 0s as separators. Then there is an automaton computable function which take a binary string of length n in L and outputs a composition of n+1 represented as a 0-separated sequence of unary numbers. The idea is to use your first algorithm, but instead of storing $i$ as a variable before writing it, we write it down as we go along.

The second algorithm does not correspond to an automaton computable function, however, because this sorting cannot be done with a fixed, finite amount of memory.

$\endgroup$
  • 1
    $\begingroup$ This seems to be very close to what I want! Indeed, right now I cannot think of an 'explicit' bijection that cannot be done with finite memory. Initially I thought one would need polynomial memory (as proposed in mathoverflow.net/a/323826), but perhaps this is not necessary! $\endgroup$ – Martin Rubey Feb 25 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.