I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?
how can i prove that square root of n is space constructible
-
1@Orgad, when dealing with space complexity we normally use separate input (read only), output (write only), and working (r/w) tapes. The space is working tape space. – 2012-01-31
1 Answers
Definition of space-constructible functions goes like this:
A function $f$ is space-constructible if there is a TM that, on input $1^n$, uses $\Theta(f(n)$ cells of the TM.
There might be slightly different version of this definition, but the point is that you can prove that a function is space-constructible simply by constructing a multi-tape TM that computes it and uses only $f(n)$ cells on every tape excluding the input tape (because you always need $n$ cells to read the input). However, you cannot write symbols on the first tape - it is read-only.
So for your example, such TM would be quite easy:
Lets have a 3-tape TM that uses the first tape for the input, second tape starts with the string "1" on it and the third tape is used for the output and is initially blank Note that I compute the function only in natural numbers (so lets assume $f(n) = \lceil \sqrt{n} \rceil$)!
You read the string on your second tape and move the appropriate number of cells on the input tape to the right. If you reach end of the second tape, you write "1" on your third output tape and move to the right and reset the position on second tape. Then you check the number of ones on your second tape and your third tape. If they are equal but you have not reached the end of the input yet, you have to continue. Increment the string on your second tape and reset everything on your third tape.
Continue until you reached the end of your input. You can easily see, that the third and second tape will finally have the square root on them and you wont need more that $\lceil \sqrt{n} \rceil$ cells.
Lets demonstrate it on a number $4$ ($x$ marks the head position before the cell):
input: x1111 -> 1x111 -> wait for check -> x1111 -> 11x11 -> 1111x -> end of input
second: x1 -> 1x -> check length and increment-> x11 -> 11x -> check and reset position -> x11
third: xB -> 1x -> check length and reset-> xB -> 1x -> check -> 11x -> check length and FINISH
If the number does not have a natural square root, we simply write one 1 on the third tape and output it. I hope its clear now.