This 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)&gt;=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 = &quot;11&quot; 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 &quot;1&quot; we read write a &quot;1&quot; 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 &quot;1&quot; we read write a &quot;1&quot; 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).