I've got two log-space programs F and G. Program F will get input in array A[1..n] and he will create the output array B[1..n]. Program G will get the input array B which has the program F created and create from him the output array C[1..n] I have to write a proof that there exist log-space program H, which will get input Array A and create from him corresponding array C. But I can't find the correct way to write it. Log-space program Log-space is the program which use O(log n) bites of memory. Here are some conditions you have to keep: You have to use only variable which has to be simple integer type. (for example int in C++, longint in Pascal) Allowed range of integer is defined: if n is a size of input then we can save into variables only values which are polymonial sized based on n. for example: we can have variable which can take on value -n...n, values -3n^5...3n^5 also values -4...7 but we can't have variable which will take on values 0...2^n Any other types of variables aren't allowed. (array and iterators aren't allowed too) Exception from the rules about has input and output. Input will be available in special variables(mostly arrays) which can your program only read and the output can your program only write 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 array of integers n- input variable, the number of elements A- input variable, the array of integers m- output variable, the position of maximum i.j- working variables var n: integer; A: array [1..n] of integer; m: integer; i, j: integer; begin j := 1; for i := 2 to n do if A > A[j] then j := i; [*]m := j; [*]end; The only two variables here are j and i and they evidently take values 1...n. Therefore all conditions are fulfilled and it really is a log-space program.
