Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:

  • $f$ is efficiently computable
  • $f$ is a bijection
  • $f$ is pseudorandom (not necessarily cryptographically)
  • Given some interval $[a,b]$ and a regular expression $r$, we can efficiently test if there exists $n \in N \cap[a,b]$ such that $f(n)$ satisfies $r$.

Does such a $f$ exist?

The tricky part is finding a function that satisfies both the second and fourth requirement.

One thought I had was to define $f(x) = c + px \pmod{|L|}$ for some constant $c$ and prime $p$. This satisfies the first three properties, but I don't think its regex searchable.

(The motivation is that such a $f$ would amount to a searchable library of Babel.)

  • $\begingroup$ What do you mean by pseudorandom? Looks random? How about the following: pick a permutation $\pi$ on $\{1,\ldots,n\}$, and for each $1 \leq i \leq n$ pick a permutation $\sigma_i$ on the alphabet. Replace $x_1\ldots x_n$ by $\sigma_1(x_{\pi(1)}) \ldots \sigma_n( x_{\pi(n)} )$. $\endgroup$ – Yuval Filmus Jun 11 '18 at 14:39
  • $\begingroup$ @YuvalFilmus Yes, looks random. For example, half of the bits should change (on average). $\endgroup$ – PyRulez Jun 11 '18 at 14:46
  • $\begingroup$ How about my suggestion, then? $\endgroup$ – Yuval Filmus Jun 11 '18 at 14:47
  • 1
    $\begingroup$ Unless you define what pseudorandom means for you, it is impossible to tell what you mean by it. Please try to define what you mean by pseudorandom. Be as explicit as possible. We cannot read your mind. $\endgroup$ – Yuval Filmus Jun 11 '18 at 14:56
  • 1
    $\begingroup$ If there are any other "obvious" assumptions, that for example makes regex searching possible, please include them as well. Nothing is obvious for us. You have to state everything to the fullest extent. $\endgroup$ – Yuval Filmus Jun 11 '18 at 14:57

Your Answer

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

Browse other questions tagged or ask your own question.