Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ steps and for each $n$ there exists some input of length $n$ on which $M$ makes exacltly $f(n)$ steps.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is fully time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps.

Q1: Does there exist a function which is time-construcible and not fully time-constructible?

The answer is yes (see this answer), if $EXP-TIME \neq NEXP-TIME$. Can the condition for "yes" be strengthened to $P\neq NP$? Can "yes" be proven?

Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?

Q3: What are the "provable" reasons for believing that all nice functions are fully time-constructible?

The paper
Kojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)
partially answers Q3. The partial summary and upgrade of it is in this answer. I take Q3 as answered.

Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See this question for more.

share|improve this question
    
Curious -- could you point me to a reference for these definitions? I am not familiar with constructible functions, and I can't find these definitions online (it's also not obvious to me whether they're equivalent to e.g. the wikipedia ones). –  usul Jan 9 '13 at 16:39
    
@usul The reference is: J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science, 1979 The same definition can be found here: cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html –  David G Jan 10 '13 at 11:04
add comment

1 Answer 1

In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.

Q3:

Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon>0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...

To continue with examples of fully time-constructible functions, one can prove that if $f_1$ and $f_2$ are fully time-constructible, then $f_1+f_2$, $f_1f_2$, $f_1^{f_2}$ and $f_1\circ f_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.

It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).

Let us also comment the definition from Wikipedia article: A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time. We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.

Q1:

This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function $$f(n)=\left\{\begin{array}{ll} 8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$$

I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:

  • on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
  • then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
  • accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.

Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.

We can make $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:

  • on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
  • if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.

Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.

The following algorithm solves $L$:

  • on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
  • compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.

share|improve this answer
3  
Very nice! [padding to make the comment box happy] –  Emil Jeřábek Jan 14 '13 at 16:37
1  
A very similar idea to the one presented in the answer to the question Q1 is also used here. –  David G Jan 14 '13 at 20:35
add comment

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.