Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a function $f$ fully space-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, halts after using exactly $f(n)$ cells. Consider this function: \begin{equation*} f(n) = \begin{cases} n^3, & \text{if}\ n = 3k \ for \ k \in \mathbb{N} \ and \ 2^n, & \text{otherwise} \end{cases} \end{equation*}

Is $f(n)$ time-constructible and/or space constructible? Also, what is the intuition behind considering time/space constructible functions in complexity theory? Will things be any different if we include non-constructible time/space functions?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

f(n) is both time- and space-constructable. $M$ converts the input to binary, performs the necessary computations, and then spins for the appropriate number of steps.

Constructable functions are primarily considered in order to simplify technical issues in proofs. For example, consider the Time Hierarchy Theorem, which essentially says that having more time allows you to solve more stuff.

The formal statement is: Given a time-constructable function $f(n)$ and a function $g(n)=\omega(f(n)\log f(n))$, there exists a language decidable in $TIME(g(n))$ but not in $TIME(f(n))$.

The proof is by diagonalization. Construct a machine $M$ which, on input $x$, simulates machine $x$ on input $x$ for $f(n)$ steps. If $x(x)$ halts within that time bound, $M$ outputs the opposite. If $x(x)$ hasn't halted, $M$ rejects (arbitrarily). The simulation can be done using $\log f(n)$ overhead, and the theorem follows.

In order for the proof to work, $M$ needs to be able to count $f(n)$ steps, and it needs to do so efficiently. Otherwise, the running time of $M$ won't be bounded by $g(n)$. Time-constructability is exactly the criteria needed to allow the proof to work.

Since basically every function of interest is time-constructable, there isn't much point in removing the technicality. Actually, in the case of the time hierarchy theorem, removing the constructability requirement makes the theorem spectacularly false. The Blum Gap Theorem says that given any function $r(n)$, such as $2^n$, there exists a function $f(n)$ such that $TIME(f(n))=TIME(f(r(n)))$. Obviously, this $f$ is not time-constructable.

share|improve this answer
    
Thanks! that was a great answer! –  Nikhil Mar 31 '11 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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