### Thread: Log-space program proof

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0

#### Log-space program proof

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[i] > 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.
2. Are you...asking us to do your theoretical comp sci homework for you?
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0
I just want to know the way how can I prove this correctly.
4. It should be in your textbook. Or ask your teacher.

Also, if you copied and pasted this from your assignment, you may want to drop this course. There's some misspellings of critical words like "bytes" and "polynomial" that, if your teacher wrote them, makes me think they're not going to do a good job teaching you.