7
$\begingroup$

I've got two log-space programs $F$ and $G$.

  • Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
  • Program $G$ will get as input $B$ as created by $F$ and create from it the output array $C[1..n]$.

I have to write a proof that there exist a log-space program $H$, which will get input Array $A$ and create from it corresponding array $C$. But I can't find the correct way to write it. How is this done?


A log-space program is a program which uses $O(\log n)$ bits of memory. Here are some conditions you have to keep:

  1. You have to use only variables which have simple integer type (for example int in C++, longint in Pascal).

  2. Allowed range of integer is defined: if $n$ is the size of the input we can save into variables only values which are polymonial sized based on $n$.

    For example: we can have variables which can takes on values in $[-n...n]$, $[-3n^5...3n^5]$ or also values $[-4...7]$, but we can't have variables which will take on values in $[ 0...2^n]$. No other types of variables are allowed, neither are arrays and iterators.

  3. Exceptions from the rules about are input and output. Input will be available in special variables (mostly arrays) which your program can only read from, and the output can only be written to other special variables. So you can't read from output, and you can't increase values of input variables etc.

  4. Your programs can't use recursion.

Example of log-space program written in Pascal (so everyone can understand it) which will find the largest number in the array of integer

    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

The only two variables here are j and i and they evidently take values in $[1...n]$. Therefore all conditions are fulfilled and it really is a log-space program.

$\endgroup$

migrated from cstheory.stackexchange.com Nov 9 '12 at 6:25

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ This is a standard assignment in undergraduate introduction to computational complexity courses. $\endgroup$ – Kaveh Nov 9 '12 at 6:25
  • 1
    $\begingroup$ Hint: How much space is required to compute B[i]? How does producing B at will helps in running $G$? $\endgroup$ – Yuval Filmus Nov 9 '12 at 13:00
3
$\begingroup$

The idea here is that we can't compute the output of the first algorithm completely because it can take more than logarithmic space (it can be polynomially large). But we don't need to if we are intelligent. What we can do is simulate the second algorithm and produce the bits it needs from the output of the first algorithm on-line. In other words, we will simulate the second machine, when it wants to read bit $i$ from its input, i.e. the bit $i$ from the output of the first machine, we stop the simulation of the second machine, simulate the first and count (but not store) the bits it outputs until it outputs the $i$th bit at which time we can stop the simulation of the first machine and continue with the simulation of the second machine as we now have the value of what it wanted to read.

$\endgroup$
  • $\begingroup$ Thanks for pointing out this argument! By any chance, do you know whether this simulation trick has a standard name, and if there is a standard textbook where it is presented in more detail? $\endgroup$ – a3nm Mar 13 '17 at 13:34
  • 1
    $\begingroup$ iirc it should be in Arora and Barak. In proof complexity we call $\{(x,i,b) \mid (f(x))_i =b\}$ the bit-graph of $f$. I think I also heard people call it on-the-fly/on-demand computation of intermediate results. $\endgroup$ – Kaveh Mar 13 '17 at 19:18
  • 1
    $\begingroup$ Thanks a lot! Indeed it is in Arora and Barak, Definition 4.16, where it is called "implicitly logspace computable". $\endgroup$ – a3nm Mar 13 '17 at 20:13

Your Answer

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