<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**: @username_1 `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**: @username_1  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**: @username_1 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**: @username_1 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

