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?

  • 1
    $\begingroup$ I don't know what space-constructible means. I know $\sqrt n$ is "Euclid-constructible," that is, I can show you how to construct it with ruler and compass, if that's what you want. $\endgroup$ – Gerry Myerson Jan 28 '12 at 22:02
  • 3
    $\begingroup$ @Gerry: The tag says "complexity," so... $\endgroup$ – anon Jan 28 '12 at 22:10
  • 1
    $\begingroup$ Thanks. space-constructible means that it is possible to construct in o(n) space from 1^n to the binary representation of f(n). in our case f(n) is sqrt. Maybe the Euclid-constructible can help. $\endgroup$ – Eyal Golan Jan 28 '12 at 22:17
  • 4
    $\begingroup$ @anon, my comment was intended to extract some useful information from OP. I think it succeeded. $\endgroup$ – Gerry Myerson Jan 28 '12 at 23:11
  • 4
    $\begingroup$ You don't need anything nearly so complicated as Newton - keep in mind that there are no time bounds on the construction. Just test all the numbers $t$ from 1 forward until you find one with $t^2\gt n$. This is easy to do in $O(\log n)$ space just by using binary. $\endgroup$ – Steven Stadnicki Jan 28 '12 at 23:36

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.