#1
  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. #2
  3. Sarcky
    Devshed Supreme Being (6500+ posts)

    Join Date
    Oct 2006
    Location
    Pennsylvania, USA
    Posts
    10,866
    Rep Power
    6351
    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.
  4. #3
  5. 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.
  6. #4
  7. Sarcky
    Devshed Supreme Being (6500+ posts)

    Join Date
    Oct 2006
    Location
    Pennsylvania, USA
    Posts
    10,866
    Rep Power
    6351
    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.

IMN logo majestic logo threadwatch logo seochat tools logo