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:
You have to use only variables which have simple integer type (for example
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.
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.
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
i and they evidently take values in $[1...n]$. Therefore all conditions are fulfilled and it really is a log-space program.