<h3>Linear functions: definition</h3>

<p>Let's define a linear function as one expressible as an untyped λ-calculus term with the added restriction that no lambda argument can be used twice. </p>

<h3>Linear functions: example</h3>

<p>Many functions can be defined that way. For example, the successor of a binary string (interpreted as an integer) could be defined as (in Idris):</p>

<pre><code>data Bit = O | I

succ : List Bit -&gt; List Bit
succ bits = case bits of
  b :: bs =&gt; (case b of
    O =&gt; \ bs0 =&gt; I :: bs0
    I =&gt; \ bs1 =&gt; O :: succ bs1) bs
  [] =&gt; []
</code></pre>

<p>That function is linear in the above sense because it could be translated to the linear untyped λ-calculus. Pattern-matching could be expressed with Scott-encodings, and we avoided using the argument <code>bs</code> twice with extra lambdas. Of course, recursion isn't expressible on that language (the Y-combinator and similar require non-linear arguments), so this definition is actually illegal, but, if we unrolled that function a few levels deep, we could still implement a <code>succ : Vect K Bit -&gt; Vect K Bit</code>, for bit lists of bounded depth <code>K</code>. That's OK for the purpose of the question. Let's assume a fixed finite <code>K</code> and abbreviate <code>Vect K Bit</code> as <code>Bits</code>. </p>

<h3>The question</h3>

<p>Given an arbitrary linear (in the sense above) function <code>f : Bits -&gt; Bits</code>, can the non-linear function <code>repeatF : Integer -&gt; Bits -&gt; Bits</code>, which applies <code>f</code> <code>n</code> times to a bit-string, always be implemented in polynomial (or at least sub-exponential) time with respect to the size of the binary integer <code>n</code>, and such that its code size grows at most polynomially when we increase <code>K</code>?  In other words, is the running time of computing $f^n(x)$ polynomial in $n$? I care only about the dependence on $n$; you can think of the size of $x$ as fixed.</p>

<h3>Example</h3>

<p>For the example function defined above, <code>succ</code>, the answer is yes. Of course, if we define <code>repeat(n,x)</code> naively, then it'll take exponential time with respect to <code>n</code>:</p>

<pre><code>repeatSucc : Integer -&gt; List Bit -&gt; List Bit
repeatSucc 0 x = x
repeatSucc n x = succ (repeatSucc (n - 1) x)
</code></pre>

<p>But by noticing that <code>repeatSucc n x</code> is equivalent to addition, we can implement it in polynomial time and space with known addition algorithms. This makes me wonder whether something similar is true for all functions <code>f</code> defined in the style above (or, of course, how we can prove that's not the case).</p>

<hr>

<h3>Note:</h3>

<p><em>I'm analyzing the complexity of <code>repeatF(n, x)</code> with respect to <code>n</code>, which is a binary non-negative integer and could be potentially infinite. The input <code>x</code> has constant size, but that is irrelevant, it is just the initial state of the iteration. You can't build a finite size lookup table for a potentially infinite argument. Even if you could, the size of <code>repeatF</code> is limited by a polynomial function of the constant depth <code>K</code>, so you can't fit a lookup table for the entire image. I'm, less formally, in essence, asking if, for any "simple" linear function like <code>succ</code>, there is a succinct algorithm to compute its repeated application quickly. Please, consider this informal intuition if my concrete formalization has further issues.</em></p>

CC BY-SA 3.0
2017-09-11T06:46:42.240Z
Your latest edits don't seem to make sense (to me).  If $K$ is a constant (or "bounded"), it makes no sense to talk about algorithms whose space usage is polynomial in $K$.  A polynomial of a constant is a constant.  And since $f$ is fixed (so $K$ is fixed) and $n$ is varying, we can't talk about the asymptotic space usage of `repeatF` as a function of $K$.
D.W.
CC BY-SA 3.0
2017-09-11T08:49:58.407Z
@D.W. `K` is fixed for a single problem, but now visualize we're able to change it (and generate a new problem). I want the *code size* of `repeatF` not to grow exponentially as we change `K` (which would happen if you inline a lookup table on its definition). Makes sense? This is just to specifically exclude those non-natural algorithms.
MaiaVictor
CC BY-SA 3.0
2017-09-11T12:04:06.087Z
I don't understand your setup.  Is `f` of type signature $\{0,1\}^K \to \{0,1\}^K$ or $\{0,1\}^\infty \to \{0,1\}^\infty$?  If the latter I don't understand your comments about how the code above is legal -- it sounds like you are saying "this code is illegal, but just imagine if it weren't", which I can't understand -- the problem statement forbids that code but you want me to pretend it's allowed?  If the former, I don't see how you can talk about asymptotics as a function of $K$.  Right now we're talking about a single fixed `f` and `repeatF`, and $n$ is able to vary.  (continued)
D.W.
CC BY-SA 3.0
2017-09-11T12:04:15.453Z
It's not clear how you'd deal with changing $K$, since that also requires changing `f` (are we talking about "for every infinite family of `f_K` there exists an infinite family of `repeatf_K`" or something?) -- basically, it doesn't seem formulated in a form where one can use asymptotic analysis in the way you want (yet).
D.W.
CC BY-SA 3.0
2017-09-11T14:12:48.580Z
@D.W.  yes, for each fixed depth you can pick, there is a `repeatf_K` defined for that depth, that is what I mean. If your algorithm uses lookup table, the size of `repeatf_K` grows exponentially as `K` grows, because, for example, for `K = 3`, you have `({0,1},{0,1},{0,1}) -> ({0,1},{0,1},{0,1}) `, which needs a lookup table of size $2^3$. That way, I'm specifically looking for a polynomial `repeatf_K` function family which, for any finite `K`, can be defined for tuples of `K` bits with a linear calculus term of size `O(poly(K))`.
MaiaVictor
CC BY-SA 3.0
2017-09-11T15:47:53.543Z
@D.W. the recursive function isn't allowed, but the bounded depth ones are. What's why I needed them. To reformulate this with recursion, I'd need an answer to [this](https://cstheory.stackexchange.com/questions/38979/is-it-possible-to-use-arbitrary-fixpoint-values-on-eal-without-losing-strong-nor) question, "how can we have recursion on linear variants of the λ-calculus"?
MaiaVictor
CC BY-SA 3.0
2017-09-11T19:37:16.623Z
If you have a family of $f$'s, i.e., $f_k$ for each $k \in \mathbb{N}$, then the linearity requirement becomes a no-op: for every function $f:\{0,1\}^k \to \{0,1\}^k$ there exists a way to implement as a linear function.  So the question can be separated from linearity and basically becomes about iterating any arbitrary infinite family of functions \{f_k : \{0,1\}^k \to \{0,1\}^k : k \in \mathbb{N}\}$.
D.W.
CC BY-SA 3.0
2017-09-13T18:25:33.933Z
@D.W. wait, how, for every `f : {0,1}^k -> {0,1}^k` there's a way to implement it as a linear function? Say `f_k(x)` is the family of functions that take the discrete logarithm of `x` (a `k-bit` integer)... how will you implement it as a linear λ-calculus term with size of the `f` bounded at `poly(k)`?
MaiaVictor
CC BY-SA 3.0
2017-09-13T19:32:10.593Z
For any fixed $k$ and any function $f_k:\{0,1\}^k \to \{0,1\}^k$, you can write linear code that implements the function : build a big case statement with $2^k$ cases (it implements the truth table of the function).  This is basically the difference between a uniform model of computation vs a non-uniform model of computation.
D.W.
CC BY-SA 3.0
2017-09-13T19:32:50.107Z
Maybe you want a single piece of code for all $k$, rather than one code per $k$; i.e., you have code that implements some function $f:\{0,1\}^* \to \{0,1\}^*$, with the promise that the length of $f(x)$ will always be equal to the length of $x$, and you want the code to be linear.  If so it seems like all of this needs specified carefully.  I still don't understand the "this isn't actually legal but we could unroll it so let's pretend it is" business in the 2nd paragraph of your question.
D.W.
<cc.complexity-theory><functional-programming>
Can $f^{2^N}(x)$ be computed in polynomial time when $f$ is linear?
MaiaVictor
# Can $f^{2^N}(x)$ be computed in polynomial time when $f$ is linear?

(Asked by: username_0 on 2017-09-04)

### Linear functions: definition

Let's define a linear function as one expressible as an untyped λ-calculus term with the added restriction that no lambda argument can be used twice.

### Linear functions: example

Many functions can be defined that way. For example, the successor of a binary string (interpreted as an integer) could be defined as (in Idris):

```
data Bit = O | I

succ : List Bit -> List Bit
succ bits = case bits of
  b :: bs => (case b of
    O => \ bs0 => I :: bs0
    I => \ bs1 => O :: succ bs1) bs
  [] => []

```

That function is linear in the above sense because it could be translated to the linear untyped λ-calculus. Pattern-matching could be expressed with Scott-encodings, and we avoided using the argument `bs` twice with extra lambdas. Of course, recursion isn't expressible on that language (the Y-combinator and similar require non-linear arguments), so this definition is actually illegal, but, if we unrolled that function a few levels deep, we could still implement a `succ : Vect K Bit -> Vect K Bit`, for bit lists of bounded depth `K`. That's OK for the purpose of the question. Let's assume a fixed finite `K` and abbreviate `Vect K Bit` as `Bits`.

### The question

Given an arbitrary linear (in the sense above) function `f : Bits -> Bits`, can the non-linear function `repeatF : Integer -> Bits -> Bits`, which applies `f` `n` times to a bit-string, always be implemented in polynomial (or at least sub-exponential) time with respect to the size of the binary integer `n`, and such that its code size grows at most polynomially when we increase `K`? In other words, is the running time of computing $f^n(x)$ polynomial in $n$? I care only about the dependence on $n$; you can think of the size of $x$ as fixed.

### Example

For the example function defined above, `succ`, the answer is yes. Of course, if we define `repeat(n,x)` naively, then it'll take exponential time with respect to `n`:

```
repeatSucc : Integer -> List Bit -> List Bit
repeatSucc 0 x = x
repeatSucc n x = succ (repeatSucc (n - 1) x)

```

But by noticing that `repeatSucc n x` is equivalent to addition, we can implement it in polynomial time and space with known addition algorithms. This makes me wonder whether something similar is true for all functions `f` defined in the style above (or, of course, how we can prove that's not the case).

---

### Note:

*I'm analyzing the complexity of `repeatF(n, x)` with respect to `n`, which is a binary non-negative integer and could be potentially infinite. The input `x` has constant size, but that is irrelevant, it is just the initial state of the iteration. You can't build a finite size lookup table for a potentially infinite argument. Even if you could, the size of `repeatF` is limited by a polynomial function of the constant depth `K`, so you can't fit a lookup table for the entire image. I'm, less formally, in essence, asking if, for any "simple" linear function like `succ`, there is a succinct algorithm to compute its repeated application quickly. Please, consider this informal intuition if my concrete formalization has further issues.*

**Tags:** cc.complexity-theory, functional-programming

> **Comments:**
> **username_1**: Your latest edits don't seem to make sense (to me).  If $K$ is a constant (or "bounded"), it makes no sense to talk about algorithms whose space usage is polynomial in $K$.  A polynomial of a constant is a constant.  And since $f$ is fixed (so $K$ is fixed) and $n$ is varying, we can't talk about the asymptotic space usage of `repeatF` as a function of $K$.  
> **username_0**: @D.W. `K` is fixed for a single problem, but now visualize we're able to change it (and generate a new problem). I want the *code size* of `repeatF` not to grow exponentially as we change `K` (which would happen if you inline a lookup table on its definition). Makes sense? This is just to specifically exclude those non-natural algorithms.  
> **username_1**: I don't understand your setup.  Is `f` of type signature $\{0,1\}^K \to \{0,1\}^K$ or $\{0,1\}^\infty \to \{0,1\}^\infty$?  If the latter I don't understand your comments about how the code above is legal -- it sounds like you are saying "this code is illegal, but just imagine if it weren't", which I can't understand -- the problem statement forbids that code but you want me to pretend it's allowed?  If the former, I don't see how you can talk about asymptotics as a function of $K$.  Right now we're talking about a single fixed `f` and `repeatF`, and $n$ is able to vary.  (continued)  
> **username_1**: It's not clear how you'd deal with changing $K$, since that also requires changing `f` (are we talking about "for every infinite family of `f_K` there exists an infinite family of `repeatf_K`" or something?) -- basically, it doesn't seem formulated in a form where one can use asymptotic analysis in the way you want (yet).  
> **username_0**: @D.W.  yes, for each fixed depth you can pick, there is a `repeatf_K` defined for that depth, that is what I mean. If your algorithm uses lookup table, the size of `repeatf_K` grows exponentially as `K` grows, because, for example, for `K = 3`, you have `({0,1},{0,1},{0,1}) -> ({0,1},{0,1},{0,1}) `, which needs a lookup table of size $2^3$. That way, I'm specifically looking for a polynomial `repeatf_K` function family which, for any finite `K`, can be defined for tuples of `K` bits with a linear calculus term of size `O(poly(K))`.  
> **username_0**: @D.W. the recursive function isn't allowed, but the bounded depth ones are. What's why I needed them. To reformulate this with recursion, I'd need an answer to [this](https://cstheory.stackexchange.com/questions/38979/is-it-possible-to-use-arbitrary-fixpoint-values-on-eal-without-losing-strong-nor) question, "how can we have recursion on linear variants of the λ-calculus"?  
> **username_1**: If you have a family of $f$'s, i.e., $f_k$ for each $k \in \mathbb{N}$, then the linearity requirement becomes a no-op: for every function $f:\{0,1\}^k \to \{0,1\}^k$ there exists a way to implement as a linear function.  So the question can be separated from linearity and basically becomes about iterating any arbitrary infinite family of functions \{f_k : \{0,1\}^k \to \{0,1\}^k : k \in \mathbb{N}\}$.  
> **username_0**: @D.W. wait, how, for every `f : {0,1}^k -> {0,1}^k` there's a way to implement it as a linear function? Say `f_k(x)` is the family of functions that take the discrete logarithm of `x` (a `k-bit` integer)... how will you implement it as a linear λ-calculus term with size of the `f` bounded at `poly(k)`?  
> **username_1**: For any fixed $k$ and any function $f_k:\{0,1\}^k \to \{0,1\}^k$, you can write linear code that implements the function : build a big case statement with $2^k$ cases (it implements the truth table of the function).  This is basically the difference between a uniform model of computation vs a non-uniform model of computation.  
> **username_1**: Maybe you want a single piece of code for all $k$, rather than one code per $k$; i.e., you have code that implements some function $f:\{0,1\}^* \to \{0,1\}^*$, with the promise that the length of $f(x)$ will always be equal to the length of $x$, and you want the code to be linear.  If so it seems like all of this needs specified carefully.  I still don't understand the "this isn't actually legal but we could unroll it so let's pretend it is" business in the 2nd paragraph of your question.  

---

## 0 answers

