Yioop - PHP Search Engine

Practice final problem 7.

Originally Posted By: ngswamy

Prove that n^2 is a proper complexity function:

We need to satisfy two property:
* f is nondecreasing
* there is a deterministic TM M that when started with x on the input tape, runs for t=O(|x|+f(|x|)) steps, uses at most O(f(|x|)) space, and outputs to an output tape the string I^f(|x|)

We know that n^2 is a non-decreasing function

For the second property, create a machine M, which takes input n and outputs n^2 using n^2 space on the tape and takes O(|n| + f(|n|)) steps:The machine works as follows:

1.Replace the first two inputs of n with A (if the input length n is 1, then 1 will be replaced with A, and when it tries to replace the next A it will reach a space in which it will move on to replace the A back with 1 and then accepts).
2. Then read each input from the original input moving right from A on the tape. If you read an A or a 1 on the original input, move to the left of the first A and when you read an empty spot, mark down a one. (As you read each symbol from the original input you should replace it with A or 1, depending on whether it is an A or a 1 so that you know where you left off.)
3. After that, move to the right most A and if you read a 1, replace it with an A and repeat the second step. Keep doing this until you reach a empty space on the right side of the tape.
4. Once you reach the empty space on the right side of the tape, go back and replace any A with a 1. Then move to the right until you read an empty space, and then accept.

State the deterministic time hierarchy theorem as presented in class:
If f(n)>=n is a proper complexity function, then the class TIME(f(n)) is strictly contained in TIME(f(2n+1)^3).

Richelle Limun
James Yu
Cameron Taslim
Nanda Guruswamy

'''Originally Posted By: ngswamy''' Prove that n^2 is a proper complexity function: We need to satisfy two property: * f is nondecreasing * there is a deterministic TM M that when started with x on the input tape, runs for t=O(|x|+f(|x|)) steps, uses at most O(f(|x|)) space, and outputs to an output tape the string I^f(|x|) We know that n^2 is a non-decreasing function For the second property, create a machine M, which takes input n and outputs n^2 using n^2 space on the tape and takes O(|n| + f(|n|)) steps:The machine works as follows: 1.Replace the first two inputs of n with A (if the input length n is 1, then 1 will be replaced with A, and when it tries to replace the next A it will reach a space in which it will move on to replace the A back with 1 and then accepts). 2. Then read each input from the original input moving right from A on the tape. If you read an A or a 1 on the original input, move to the left of the first A and when you read an empty spot, mark down a one. (As you read each symbol from the original input you should replace it with A or 1, depending on whether it is an A or a 1 so that you know where you left off.) 3. After that, move to the right most A and if you read a 1, replace it with an A and repeat the second step. Keep doing this until you reach a empty space on the right side of the tape. 4. Once you reach the empty space on the right side of the tape, go back and replace any A with a 1. Then move to the right until you read an empty space, and then accept. State the deterministic time hierarchy theorem as presented in class: If f(n)>=n is a proper complexity function, then the class TIME(f(n)) is strictly contained in TIME(f(2n+1)^3). Richelle Limun James Yu Cameron Taslim Nanda Guruswamy

-- Practice final problem 7

Originally Posted By: lambert

I cant seem to visualize or follow the steps on how the TM M is working.

Cant we make this easy this with a 3-tape machine S by doing the following
S takes the input string 1^n. So if n =2, x = "11"
S on input x:
1.Copies x to tape-2
2. rewind both tapes 1 and 2
3. Advances one position to the right on tape 2 and see if we read an empty space. If so S halts.
4. Scan right on the input tape until we hit an empty square. For every "1" we read write a "1" on tape 3.
5. Advances one position to the right on tape 2 and see if we read an empty space. If so S halts.
6. Now scan left on the input tape until we hit an empty square. For every "1" we read write a "1" on tape 3.
7. go to step 3

Eventually tape 2 will hit an empty square and the machine will halt and tape 3 holds n-squared 1's
we can clearly see that this machine runs in n+(n^2) steps and outputs a string n^2 long

'''Originally Posted By: lambert''' I cant seem to visualize or follow the steps on how the TM M is working. Cant we make this easy this with a 3-tape machine S by doing the following S takes the input string 1^n. So if n =2, x = "11" S on input x: 1.Copies x to tape-2 2. rewind both tapes 1 and 2 3. Advances one position to the right on tape 2 and see if we read an empty space. If so S halts. 4. Scan right on the input tape until we hit an empty square. For every "1" we read write a "1" on tape 3. 5. Advances one position to the right on tape 2 and see if we read an empty space. If so S halts. 6. Now scan left on the input tape until we hit an empty square. For every "1" we read write a "1" on tape 3. 7. go to step 3 Eventually tape 2 will hit an empty square and the machine will halt and tape 3 holds n-squared 1's we can clearly see that this machine runs in n+(n^2) steps and outputs a string n^2 long

-- Practice final problem 7

Originally Posted By: ngswamy

If you use a 3-tape dosen't this mean that you would be using a 3n^2 space?

Sorry, the algorithm is a bit hard to follow.
Say you have input 1111
First you would have: AA11
Then you read through the original input one time, and each time you read an A or a 1 on the original input, write a 1 to the left of the the leftmost character of the input.

1111AA11
^
Next step:
1111AAA1
11111111AAA1
11111111AAAA
111111111111AAAA

Then replace all A's with 1's

Final tape: 1111111111111111
n now went to n^2 on the tape while still using n^2 space.... hope this helps.
Yours might work too, I'm just not sure if it's done in the n^2 space.

'''Originally Posted By: ngswamy''' If you use a 3-tape dosen't this mean that you would be using a 3n^2 space? Sorry, the algorithm is a bit hard to follow. Say you have input 1111 First you would have: AA11 Then you read through the original input one time, and each time you read an A or a 1 on the original input, write a 1 to the left of the the leftmost character of the input. 1111AA11 ^ Next step: 1111AAA1 11111111AAA1 11111111AAAA 111111111111AAAA Then replace all A's with 1's Final tape: 1111111111111111 n now went to n^2 on the tape while still using n^2 space.... hope this helps. Yours might work too, I'm just not sure if it's done in the n^2 space.

-- Practice final problem 7

Originally Posted By: lambert

Ok I see now
but I didnt use up every space on tape1 or tape 2 so the most would be n+n+(n^2) space from the slide it says:

We measure space disregarding the input and output tapes: The input tape is assumed to be read-only and we assume we also have a dedicated, write-only output tape.

http://www.cs.sjsu.edu/faculty/pollett/154.1.11s/Lec25042011.html#%283%29
So if we ignored input and output tapes the most space I used was n on tape 2

Also your algorithm for writing A and rewinding to write the 1's would seem to take longer than |x| + (|x|)^2 time wouldnt it? since you have to keep scanning back and forth after each 1 you write
Imagine on and input of 1111
To replace the first 2 inputs to A we used 2 steps tape = AA
Writing the first left most 1 takes 2 steps. tape = 1AA11
The second 1 takes 5 steps. tape = 11AA11
The third 1 takes 9 steps. tape = 111AA11
The fourth 1 takes 13 steps. tape = 1111AA11

so that would be 31 steps so far. which is larger then 4^2 and we are not even finished yet correct?

'''Originally Posted By: lambert''' Ok I see now but I didnt use up every space on tape1 or tape 2 so the most would be n+n+(n^2) space from the slide it says: We measure space disregarding the input and output tapes: The input tape is assumed to be read-only and we assume we also have a dedicated, write-only output tape. http://www.cs.sjsu.edu/faculty/pollett/154.1.11s/Lec25042011.html#%283%29 So if we ignored input and output tapes the most space I used was n on tape 2 Also your algorithm for writing A and rewinding to write the 1's would seem to take longer than |x| + (|x|)^2 time wouldnt it? since you have to keep scanning back and forth after each 1 you write Imagine on and input of 1111 To replace the first 2 inputs to A we used 2 steps tape = AA Writing the first left most 1 takes 2 steps. tape = 1AA11 The second 1 takes 5 steps. tape = 11AA11 The third 1 takes 9 steps. tape = 111AA11 The fourth 1 takes 13 steps. tape = 1111AA11 so that would be 31 steps so far. which is larger then 4^2 and we are not even finished yet correct?

-- Practice final problem 7

Originally Posted By: ngswamy

Ohh, okay..yeah then our algorithm won't work.

I think yours works right.

'''Originally Posted By: ngswamy''' Ohh, okay..yeah then our algorithm won't work. I think yours works right.

-- Practice final problem 7

Let me point out the runtime only needs to be O(|x| + (|x|)^2) not |x| + (|x|)^2. That said,
The original algorithm I think is Omega(|x|^3), Lambert's from a casual read looks O(|x| + (|x|)^2).

Let me point out the runtime only needs to be O(|x| + (|x|)^2) not |x| + (|x|)^2. That said, The original algorithm I think is Omega(|x|^3), Lambert's from a casual read looks O(|x| + (|x|)^2).