Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some polynomial of degree $Q(n)$ for some other polynomial $Q$ and with $\log(P(n))$ space with regard to some global endocing using a fixed number of symbols $s_1, \dots , s_r$.

I could find such a function that runs in polynomial time and uses polynomial space:

Given $\sigma_1 \dots \sigma_n$ Assuming $0^0 = 1$, let $i=i_1, \dots , i_k$ the indices for which $\sigma_i = 1$.

Then define $f$ as:

$f(m) = 0^{(m-i_1) \dots (m-i_k)} = \sigma_m$ for all $m=1, \dots, n$ (power here is mathematical power and not the number of repetitions function)

So $f$ is basically evaluating a polynomial of degree at most $n$, so it runs in polynomial time with regard to $n$ and clearly takes $O(n)$ and hence polynomial space.

Can there be a computable logarithmic time and space (logarithmic space to hold $f$ i.e. $|\langle f \rangle | = O(\log n)$) function with regard to $n$?

We can also simply take $f= \{(1, \sigma_1), \dots (n, \sigma_n)\}$. then $f$ runs in $\Omega(n)$ and takes $\Omega(n)$ space.

Some sequences can clearly have such $f$. E.g. take the sequence $\sigma_1 \dots \sigma_n = 0 \dots 0$ then $f \equiv 0$ is constant space to encode and constant time to compute.

Another simple example take the sequence $001001 \dots 001$ and define $f$ as:


  1. compute $x \equiv m \pmod 3$
  2. if $x = 1$ return $0$
  3. if $x=2$ return $0$
  4. return $1$

This is also constant space representation for $f$ and constant time to compute.

But if for example we take the sequence to be the first $n$ digits of an irrational number in binary, can there be such $f$? and in general?

  • $\begingroup$ You are looking for a way to calculate $\sigma_m$ in time and spacing depending on $n$. What is the relation between $m$ and $n$, if any? $\endgroup$ Aug 6, 2021 at 22:18
  • $\begingroup$ It seems that $f(m) = 0$ for all $m > n$. The constant zero function is easy to compute. $\endgroup$ Aug 6, 2021 at 22:19
  • $\begingroup$ What is the input, and what is the required output? Your post doesn't make that clear. $\endgroup$ Aug 6, 2021 at 22:19
  • $\begingroup$ $m \in \{1, \dots, n\}$, the input is a word $\sigma_1 \dots \sigma_n$ over $\{0,1\}$ and the output is a computable function $f: \{1, \dots, n\} \to \{0,1\} $ that takes logarithmic time with regard to $n$ to calculate $\sigma_m$, for arbitrary $m \in \{1, \dots, n \}$ $\endgroup$ Aug 6, 2021 at 23:28
  • $\begingroup$ If $f$ only accepts finitely many inputs, it is computable in constant space. $\endgroup$ Aug 7, 2021 at 3:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.