November 7th, 2012, 02:11 PM

Logspace program proof
I've got two logspace 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 logspace 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.
Logspace program
Logspace 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 logspace 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 logspace program.
November 7th, 2012, 02:27 PM

Are you...asking us to do your theoretical comp sci homework for you?
HEY! YOU! Read the New User Guide and Forum Rules
"They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." Benjamin Franklin
"The greatest tragedy of this changing society is that people who never knew what it was like before will simply assume that this is the way things are supposed to be." 2600 Magazine, Fall 2002
Think we're being rude? Maybe you
asked a bad question or you're a
Help Vampire. Trying to argue intelligently? Please
read this.
November 7th, 2012, 03:02 PM

I just want to know the way how can I prove this correctly.
November 8th, 2012, 08:44 AM

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.
HEY! YOU! Read the New User Guide and Forum Rules
"They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." Benjamin Franklin
"The greatest tragedy of this changing society is that people who never knew what it was like before will simply assume that this is the way things are supposed to be." 2600 Magazine, Fall 2002
Think we're being rude? Maybe you
asked a bad question or you're a
Help Vampire. Trying to argue intelligently? Please
read this.