0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – D.W. Sep 11 '17 at 6:46
  • $\begingroup$ @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. $\endgroup$ – MaiaVictor Sep 11 '17 at 8:49
  • $\begingroup$ 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) $\endgroup$ – D.W. Sep 11 '17 at 12:04
  • $\begingroup$ 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). $\endgroup$ – D.W. Sep 11 '17 at 12:04
  • $\begingroup$ @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)). $\endgroup$ – MaiaVictor Sep 11 '17 at 14:12

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.