<p>[Upon reading more of the comments on the question, I realized that this answers Jukka's second formulation, but the original question was actually more about Jukka's first formulation. I'll leave this answer and the comments here for discussion for a while.]</p>

<p>The problem you are trying to solve (as formalized by Jukka's second comment above) is not computable, and so in particular does not have an EXP upper bound (proof below).</p>

<p>You might also be interested in Chapter 6 of Juris Hartmanis' book "Feasible Computations and Provable Complexity Properties" which discusses the difference between the collection of languages decidable in a given time bound, and the collection of languages <em>provably</em> decidable in that time bound.</p>

<p><em>Proof:</em> Intuitively the idea is that, any algorithm $A$ can only look at finitely much data before deciding the runtime of $M$. So we can construct an $M$ for which the finite amount of data that $A$ looks at is not enough to decide even an upper bound on the runtime of $M$.</p>

<p>Formally, suppose there were some algorithm $A$ which, given the description of a Turing machine $M$ as input, with the promise that $M$ runs in time $n^c$ for some unknown constant $c$, outputs a $k$ such that $M$ runs in times at most $n^k$ (i.e., $c \leq k$). (Note that this is a promise problem: if $M$ describes a Turing machine which does not run in polynomial time, we do not care what $A$ outputs, or even if $A$ halts.)</p>

<p>Then $A$ fails on a description the following machine $M_0$. Let $n_0$ be the length of a known description $D$ of $M_0$. On input $0^n$, $M_0$ starts trying to compute $A(D)$. If it takes more than $n$ steps, $M_0$ halts. Otherwise, $M_0$ gets the output $k = A(D)$.  $M_0$ then loops for $n^{k+1}$ steps and halts. $M_0$ runs in polynomial time and so satisfies the promise, yet $A(D)$ outputs a $k$ such that $n^k$ is <em>not</em> an upper bound on the runtime of $M_0$.</p>

CC BY-SA 2.5
2011-02-02T23:51:01.723Z
Hmmmm ... Joshua, your answer seemingly implies that the question that started this whole sequence, namely, "Does BPQ^P = BAP?", or equivalently, "Is P low for BQP?", is still open ... because (as your answer implies) there is in general no P-uniform reduction of the oracular P in BQP^P to the reversible logic gates that are essential to the usual reduction methods.   You may well be right ... but this is AFAICT *not* the [consensus view](http://rjlipton.wordpress.com/2011/01/25/factoring-is-in-bqp/#comment-10471).  So, please post more! :)
John Sidles
CC BY-SA 2.5
2011-02-03T00:23:01.670Z
Hmmmm ... again ... Joshua, your answer is a good start ... but there are two concerns: (1) the run-time estimation problem surely *is* computable (for every n) by the inefficient expedient of observing the runtime for all possible, and (2) assuming that your proof can be fixed-up to show that run-time estimation is *not* in P (which is my intuition too) the question's second half is still open, namely, concretely exhibit an algorithm in P whose runtime is harder-than-P to estimate.  Despite these concerns, your reply is a wonderful start ... eventually I hope to rate it as an "answer".  :)
John Sidles
CC BY-SA 2.5
2011-02-03T00:46:13.107Z
LOL ... Joshua, one final note ... I see you are at UChicago ... where my wife, my son and I all attended ... so please let me say, our whole family sympathizes with the horrendous winter weather that you are facing today! :)  More to the point, my thinking along P-centric lines was first stimulated, not only by practical challenges in quantum systems engineering, but also by a marvelous lecture by Ketan Mulmuley, whose theme was "The mysterious complexity class P". So good luck with a Chicago-style blizzard *and* with the mysteries of P.  :)
John Sidles
CC BY-SA 2.5
2011-02-03T01:07:28.623Z
I think I understand now. My answer was to Jukka's *second* formulation of your question, which I stand by; I also agree with the consensus view. Based on your most recent comment, I think Jukka's *first* formulation is more what you are asking about, which I'll have to think more about. Oh, and upon reading further comments I see Kristoffer already anticipated what I said. I think it would be helpful if you added Jukka's first formulation to the question statement for clarification. Thanks for the well-wishes.
Joshua Grochow
CC BY-SA 2.5
2011-02-03T01:58:49.017Z
It seemed to me that Tsuyoshi Ito's formulation best captured the intent of my original question ... and was reasonably consonant with everyone else' formulation ... and most important of all, was likely to stimulate good answers ... and so I have edited the question to ask for responses specifically to Tsuyoshi's formulation.  Thanks!
John Sidles
CC BY-SA 2.5
2011-02-02T23:35:56.253Z
2011-02-03T01:20:12.030Z
2011-02-03T01:20:12.030Z
Joshua Grochow
<p>As currently asked, the answer to the question is yes, assuming that there are problems in NE (non-deterministic time $2^{O(n)}$) that require doubly-exponential time to be solved. Under the standard assumption that,  $NE\neq E$, there is a turing machine $M$ such that computation of $f(M,n)$ given $n$ cannot be done in time polynomial in $n$.</p>

<p>In general, suppose that there is a language $L$ that is in NE, and that cannot be solved in deterministic time $t(2^n)$ (plausibly, there could be such a language with $t(n) = 2^{n^\epsilon}$). Let $L&#39;$ be the language that contains only the strings of the form $1^N$ such that the $N$-th string in lexicographic order is in $L$. Thus $L&#39;$ is in NP and such that if $1^N \in L&#39;$ then it has a certificate of length $\leq N$,  but such that $L&#39;$ cannot be solved in deterministic time less than $t(N)$.</p>

<p>Define the polynomial-time turing machine $M$ so that, on input $x$ of length $N$, it decides whether $x$ is a witness for $1^N$. If it is a witness, then $M$ accepts in time, say $N^2$, otherwise it keeps going some more, and rejects after $N^3$ steps. So we see that $f(M,N)= N^2$ if $1^N \in L&#39;$, and $f(M,N) = N^3$ otherwise, and so computing $f(M,N)$ cannot be done in time less than $t(N)$</p>

CC BY-SA 2.5
2011-02-03T07:59:36.923Z
2011-02-03T07:59:36.923Z
Luca Trevisan
<p>Update #6:</p>

<p>Wow, quick service on TCS StackExchange!  Emanuele Viola has provided an answer <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable"><i>Are runtime bounds in P decidable? Answer: No</i></a>.</p>

<p>Emanuele's answer illuminates (for me) Luca Trevisan's answer <a href="https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716">Do runtimes for P require exp resources to upper-bound?  Answer: yes</a>.</p>

<p>Thus, I am becoming pretty optimistic of being able to post, pretty soon, a reasonably reliable (partial) summary of the computational complexity of runtime estimation for algorithms in P (it's harder than one might guess). </p>

<p>In the meantime, please see Emanuele's and Luca's answers.</p>

<hr>

<p>Update #5:</p>

<p>I am pleased to report steady progress toward a summary answer -- a key remaining question,  that has just been asked on TCS StackExchange, is <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable"><i>Are runtime bounds in P decidable?</i></a></p>

<p>My thanks go to all who have helped/are helping this particular researcher.</p>

<hr>

<p>Update #4:</p>

<p>As I work through the many fine comments&mdash;and Luca Trevisan's construction in particular&mdash;a summary narrative is slowly crystallizing, that eventually I will post here (once I gain sufficient confidence in it).   For now, there is a <a href="http://rjlipton.wordpress.com/2011/02/06/game-changing-conjectures-in-mathematics/#comment-10618" rel="nofollow noreferrer">preliminary draft posted on the <i>G&ouml;del's Lost Letter</i> weblog</a> ... where comments are welcome.</p>

<p>At present I grasp many of the tricks of complexity theory pretty well, but the motivating ideas beind these tricks often are opaque (to me), for reasons that Mac Lane describes:<blockquote>Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations.  In some of these cases, one can find a conceptual background.  When so, the ideas so revealed help us understand what's what.  We submit that this aim of understanding is a vital aspect of mathematics.</blockquote>It is the "understanding of what's what" that as yet has not crystallized (for me) ... and yet I am very appreciative and grateful for the help that has been given so generously, to me and to many on this fine forum. </p>

<hr>

<p>Update #3:</p>

<p>On MathOverflow, Luca Trevisan has posted <a href="https://mathoverflow.net/questions/54124/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples">an interesting new comment relating to runtime estimation</a> that (as I parse his comment) raises issues that are broadly associated to the practical feasibility of generating concrete runtime estimates.</p>

<p>I apologize for my slowness in producing a summary trace-back of these issues ... realistically it may take quite awhile to produce a summary of these questions-and-answers that respects the existing literature, and has lasting value, not only to TCS students, but to the broader community of mathematicians, scientists and engineers who care about these issues.</p>

<hr>

<p>Update #2:</p>

<p>I have rated as "accepted" <a href="https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716">Luca Trevisan's ingenious construction</a>, which answers the question as reframed by Tsuyoshi Ito.      Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).</p>

<p>It will take awhile (for me anyway) to appreciate whether Luca's $M$-machines obstruct the $P$-time uniform reduction of ${BQP}^{P}\,\to\,{BQP}$ that is at the heart of the original question posed on <em>MathOverflow</em>, that question being, <a href="https://mathoverflow.net/questions/53503/does-bqpp-bqp-and-what-proof-machinery-is-available">"Does BQP^P = BQP? ... and what proof machinery is&nbsp;available?"</a>  </p>

<p>In turn, this was a generalization of a question that was posed by Dick Lipton and Ken Regan on their weblog <i>G&ouml;del's Lost Letter and P=NP</i>, the question <a href="http://rjlipton.wordpress.com/2011/01/23/is-factoring-really-in-bqp-really/" rel="nofollow noreferrer">"Is&nbsp;Factoring Really In BQP? Really?"</a></p>

<p>After some further reflection (which may take a few days) I will attempt a summary back-trace of this chain of questions, which so enjoyably unites elements of mathematics, science and practical engineering.</p>

<p>In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!</p>

<hr>

<p>Update #1:</p>

<p>I greatly admire Tsuyoshi Ito's comment, which (because it appears below the break) I will quote here in full: </p>

<blockquote>
  <p>I think that you are asking the following. For a Turing machine M and an integer n≥0, let f(M,n) be the maximum number of steps required for M to halt on the input x over the strings x∈{0,1}^n. The question I believe you are asking here is whether there exists a polynomial-time Turing machine M such that computing f(M,n) requires time exponential in n. (Note that M is not part of the input.)</p>
</blockquote>

<p>I therefore ask that answers be addressed to Tsuyoshi's formulation (rather than my original clumsier formulation).  Keep in mind that $M\in P$ is given, so that for each $M$ we have $f(M,n)\le n^{k(M)}$ for some (unknown $M$-dependent) $k(M)$.  Moreover, please don't forget also that if your answer is "yes", then please either specify a concrete instance of M, or else, state your view as to whether M is constructible.  And if your answer is "no", then please describe (if possible) an algorithm for computing f(M,n) that requires only n-polynomial time. And please have fun too! :)</p>

<hr>

<p>Do runtimes for algorithms in P require EXP resources to upper-bound? ... are concrete examples known? </p>

<p>After some thought, I posted this question on <i>MathOverflow</i>, rather than here on <i>TCS Theory</i> in consequence of a (possibly wrong) intuition that the answers would be "yes" and "yes" ... for details, <a href="https://mathoverflow.net/questions/54124/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples">see the <i>MathOverflow</i> question</a>.</p>

<p>In the event that the answer is known to TCS <i>cognoscenti</i> to be "no"&mdash;such that a runtime bounding algorithm (itself in <i>P</i>) that encompasses all algorithms in <i>P</i>  can be concretely given&mdash;then that answer too would be very interesting and valuable.  </p>

<p>Please consider contributing an answer to this cross-disciplinary question on <i>MathOverflow</i> ... or if you prefer to post your answer(s) here in <i>TCS Theory</i>, then eventually I will summarize them on <i>MathOverFlow</i> too.  </p>

<p>Also, please accept my thanks and appreciation for this wonderful site.</p>

CC BY-SA 2.5
2011-02-02T22:04:53.837Z
I don't understand the question. Are you asking the complexity of the following problem? Input: A Turing machine. Output: An upper bound (in terms of the input size) on its running time for all inputs.
Robin Kothari
CC BY-SA 2.5
2011-02-02T22:05:04.657Z
Exactly what is the problem that you are studying? What is input, and what are the assumptions, and what is output? Perhaps something like "given Turing machine $M$ (and a promise that $M$ halts with all inputs) and integer $n$, find an integer $T$ such that $M$ halts with all inputs af length $n$ in time $\le T$"? And you would like to know if there is an algorithm that solves the problem faster than the trivial algorithm that takes $O(2^n T)$ time (simply run $M$ with all inputs)?
Jukka Suomela
CC BY-SA 2.5
2011-02-02T22:40:30.277Z
Here by "algorithm" is meant (formally) "the input tape of a (single-tape) Turing machine". Less formally, what we have in mind is the (regrettably) common circumstance that we are given a computer code that for <i>n</i>-bit inputs always terminates in <i>n</i>-polynomial time ... but the code is unaccompanied by any formal proof of this behavior ... leaving no recourse (or is there?) for run-time estimation other than exhaustive testing of exponentially many inputs. Thus one concrete answer to the question posed would be "Here is an example of such a hard-to-estimate-runtime code."
John Sidles
CC BY-SA 2.5
2011-02-02T22:53:35.000Z
Hmmmm ... didn't mean to hit return quite yet.  A key point is that the algorithm is specified to be in P; thus we are *not* asked to decide the (undecidable) halting problem.   Of course, it is natural to wonder "But how do we know that a given algorithm is in P?"  Yet the standard definition of the complexity theory class P does not require that any answer be given beyond the oracular one: "Because for all inputs of length n, the algorithm terminates in n-polynomial time."  So in essence, the question asked is, are there algorithms in P for which the oracle's answer is the only answer?
John Sidles
CC BY-SA 2.5
2011-02-02T22:59:11.027Z
Oh, are you asking something like this: "Given a Turing machine $M$ and a promise that $M$ halts in time $\le n^c$ for some unknown $c$, find a $k$ such that $M$ halts in time $\le n^k$ (for any input)?"
Jukka Suomela
CC BY-SA 2.5
2011-02-02T23:01:43.580Z
To the best of my (imprecise) grasp of the language of complexity theory, that is *precisely* what I am asking .. thank you! :)
John Sidles
CC BY-SA 2.5
2011-02-02T23:11:26.983Z
Sorry, Jukka, ... I know understand that two-paragraph comments get clipped.   There was supposed to be follow-on question asking whether "a promise that $M$ halts in time $\le n^c$" isn't precisely the restriction $M\in P$?  Also a reminder of the  proviso that for fixed $n$, we are to upper-bound the runtime of $M$ using $n$-polynomial resources ... because otherwise we might just as well do an exhaustive sampling of runtimes for EXP-many inputs.   Hopefully this comment is formatted OK.
John Sidles
CC BY-SA 2.5
2011-02-02T23:25:13.517Z
@Jukka: With this formulation it seems to me one gets an undecidable problem. @John Sidles: It seems you are also interested in a *specific* input length as well?
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-02-03T00:36:51.870Z
Reading the question on MathOverflow, I think that you are asking the following.  For a Turing machine M and an integer n≥0, let f(M,n) be the maximum number of steps required for M to halt on the input x over the strings x∈{0,1}^n.  The question I believe you are asking here is whether there exists a polynomial-time Turing machine M such that computing f(M,n) requires time exponential in n.  (Note that M is not part of the input.)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T00:54:53.003Z
Yes, to the best of my (not-expert) understanding, that is *exactly* the question intended.  Thank you very much for stating it so clearly!
John Sidles
CC BY-SA 2.5
2011-02-03T01:19:06.477Z
@John: Please edit the question so that it reflects exactly what you want to know.
Jukka Suomela
CC BY-SA 2.5
2011-02-03T01:22:56.363Z
@Tsuyoshi: I got the impression that we are looking for upper bounds, not exact running times. And if you fix $M$, and you know that $M$ halts in polynomial time, then computing an upper bound on $f(M,n)$ is easy. (Easy in the sense that an efficient algorithm exists; designing the algorithm for a given $M$ is another question.)
Jukka Suomela
CC BY-SA 2.5
2011-02-03T01:35:15.433Z
Jukka, anticipating your request, I have just now edited the question to embrace Tsuyoshi Ito's formulation of it.
John Sidles
CC BY-SA 2.5
2011-02-03T01:48:28.647Z
@Jukka: I agree that computing an _upper bound_ on f(M,n) is trivial for every fixed poly-time Turing machine M.  What I wrote in the comment was the best guess that I could come up with, though.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T02:03:27.997Z
@Jukka: "And if you fix M, and you know that M halts in polynomial time, then computing an upper bound on f(M,n) is easy. (Easy in the sense that an efficient algorithm exists; designing the algorithm for a given M is another question.)" ... Hmmm ... so if I set (for example) n=10^4, and set M = (an Python script, oracularly guaranteed to be in P, but otherwise undocumented) ... you can efficiently upper-bound f(M,n)? ... if so, please post this marvelous algorithm as an answer!
John Sidles
CC BY-SA 2.5
2011-02-03T02:17:17.737Z
@John: What Jukka said is that you can construct countably many efficient algorithms such that at least one of them gives you a correct upper bound on f(M,n) for all n.  Namely, the k-th algorithm just outputs n^k+k.  Then the promise that M is poly-time implies that there is a single k such that the k-th algorithm outputs a correct upper bound on f(M,n) for all n.  As he wrote, finding a correct k is a separate matter.  See also a [similar example](http://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2825#2825).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T02:27:53.540Z
Aha!  This is precisely the insight that I was seeking ... an algorithm exists that is correct and efficient ... but there is no efficient means---even in principle?---of validly and verifiably selecting it from an (exponentially large) set of incorrect algorithms.  I will sleep on this insight tonight ... it appears that much depends on whether validation and verification is accounted as a computational cost.  Truly, P is a tricky complexity class.  Thank you!
John Sidles
<cc.complexity-theory><time-complexity>
Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)
John Sidles
# Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

(Asked by: username_0 on 2011-02-02)

Update #6:

Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer [*Are runtime bounds in P decidable? Answer: No*](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable).

Emanuele's answer illuminates (for me) username_6's answer [Do runtimes for P require exp resources to upper-bound? Answer: yes](https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716).

Thus, I am becoming pretty optimistic of being able to post, pretty soon, a reasonably reliable (partial) summary of the computational complexity of runtime estimation for algorithms in P (it's harder than one might guess).

In the meantime, please see Emanuele's and Luca's answers.

---

Update #5:

I am pleased to report steady progress toward a summary answer -- a key remaining question, that has just been asked on TCS StackExchange, is [*Are runtime bounds in P decidable?*](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable)

My thanks go to all who have helped/are helping this particular researcher.

---

Update #4:

As I work through the many fine comments—and username_6's construction in particular—a summary narrative is slowly crystallizing, that eventually I will post here (once I gain sufficient confidence in it). For now, there is a [preliminary draft posted on the *Gödel's Lost Letter* weblog](http://rjlipton.wordpress.com/2011/02/06/game-changing-conjectures-in-mathematics/#comment-10618) ... where comments are welcome.

At present I grasp many of the tricks of complexity theory pretty well, but the motivating ideas beind these tricks often are opaque (to me), for reasons that Mac Lane describes:
> Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations. In some of these cases, one can find a conceptual background. When so, the ideas so revealed help us understand what's what. We submit that this aim of understanding is a vital aspect of mathematics.

It is the "understanding of what's what" that as yet has not crystallized (for me) ... and yet I am very appreciative and grateful for the help that has been given so generously, to me and to many on this fine forum.

---

Update #3:

On MathOverflow, username_6 has posted [an interesting new comment relating to runtime estimation](https://mathoverflow.net/questions/54124/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples) that (as I parse his comment) raises issues that are broadly associated to the practical feasibility of generating concrete runtime estimates.

I apologize for my slowness in producing a summary trace-back of these issues ... realistically it may take quite awhile to produce a summary of these questions-and-answers that respects the existing literature, and has lasting value, not only to TCS students, but to the broader community of mathematicians, scientists and engineers who care about these issues.

---

Update #2:

I have rated as "accepted" [username_6's ingenious construction](https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716), which answers the question as reframed by username_4. Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).

It will take awhile (for me anyway) to appreciate whether Luca's $M$-machines obstruct the $P$-time uniform reduction of ${BQP}^{P}\,\to\,{BQP}$ that is at the heart of the original question posed on *MathOverflow*, that question being, ["Does BQP^P = BQP? ... and what proof machinery is available?"](https://mathoverflow.net/questions/53503/does-bqpp-bqp-and-what-proof-machinery-is-available)

In turn, this was a generalization of a question that was posed by Dick Lipton and Ken Regan on their weblog *Gödel's Lost Letter and P=NP*, the question ["Is Factoring Really In BQP? Really?"](http://rjlipton.wordpress.com/2011/01/23/is-factoring-really-in-bqp-really/)

After some further reflection (which may take a few days) I will attempt a summary back-trace of this chain of questions, which so enjoyably unites elements of mathematics, science and practical engineering.

In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!

---

Update #1:

I greatly admire username_4's comment, which (because it appears below the break) I will quote here in full:

> I think that you are asking the following. For a Turing machine M and an integer n≥0, let f(M,n) be the maximum number of steps required for M to halt on the input x over the strings x∈{0,1}^n. The question I believe you are asking here is whether there exists a polynomial-time Turing machine M such that computing f(M,n) requires time exponential in n. (Note that M is not part of the input.)

I therefore ask that answers be addressed to Tsuyoshi's formulation (rather than my original clumsier formulation). Keep in mind that $M\in P$ is given, so that for each $M$ we have $f(M,n)\le n^{k(M)}$ for some (unknown $M$-dependent) $k(M)$. Moreover, please don't forget also that if your answer is "yes", then please either specify a concrete instance of M, or else, state your view as to whether M is constructible. And if your answer is "no", then please describe (if possible) an algorithm for computing f(M,n) that requires only n-polynomial time. And please have fun too! :)

---

Do runtimes for algorithms in P require EXP resources to upper-bound? ... are concrete examples known?

After some thought, I posted this question on *MathOverflow*, rather than here on *TCS Theory* in consequence of a (possibly wrong) intuition that the answers would be "yes" and "yes" ... for details, [see the *MathOverflow* question](https://mathoverflow.net/questions/54124/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples).

In the event that the answer is known to TCS *cognoscenti* to be "no"—such that a runtime bounding algorithm (itself in *P*) that encompasses all algorithms in *P* can be concretely given—then that answer too would be very interesting and valuable.

Please consider contributing an answer to this cross-disciplinary question on *MathOverflow* ... or if you prefer to post your answer(s) here in *TCS Theory*, then eventually I will summarize them on *MathOverFlow* too.

Also, please accept my thanks and appreciation for this wonderful site.

**Tags:** cc.complexity-theory, time-complexity

> **Comments:**
> **username_1**: I don't understand the question. Are you asking the complexity of the following problem? Input: A Turing machine. Output: An upper bound (in terms of the input size) on its running time for all inputs.  
> **username_2**: Exactly what is the problem that you are studying? What is input, and what are the assumptions, and what is output? Perhaps something like "given Turing machine $M$ (and a promise that $M$ halts with all inputs) and integer $n$, find an integer $T$ such that $M$ halts with all inputs af length $n$ in time $\le T$"? And you would like to know if there is an algorithm that solves the problem faster than the trivial algorithm that takes $O(2^n T)$ time (simply run $M$ with all inputs)?  
> **username_0**: Here by "algorithm" is meant (formally) "the input tape of a (single-tape) Turing machine". Less formally, what we have in mind is the (regrettably) common circumstance that we are given a computer code that for <i>n</i>-bit inputs always terminates in <i>n</i>-polynomial time ... but the code is unaccompanied by any formal proof of this behavior ... leaving no recourse (or is there?) for run-time estimation other than exhaustive testing of exponentially many inputs. Thus one concrete answer to the question posed would be "Here is an example of such a hard-to-estimate-runtime code."  
> **username_0**: Hmmmm ... didn't mean to hit return quite yet.  A key point is that the algorithm is specified to be in P; thus we are *not* asked to decide the (undecidable) halting problem.   Of course, it is natural to wonder "But how do we know that a given algorithm is in P?"  Yet the standard definition of the complexity theory class P does not require that any answer be given beyond the oracular one: "Because for all inputs of length n, the algorithm terminates in n-polynomial time."  So in essence, the question asked is, are there algorithms in P for which the oracle's answer is the only answer?  
> **username_2**: Oh, are you asking something like this: "Given a Turing machine $M$ and a promise that $M$ halts in time $\le n^c$ for some unknown $c$, find a $k$ such that $M$ halts in time $\le n^k$ (for any input)?"  
> **username_0**: To the best of my (imprecise) grasp of the language of complexity theory, that is *precisely* what I am asking .. thank you! :)  
> **username_0**: Sorry, Jukka, ... I know understand that two-paragraph comments get clipped.   There was supposed to be follow-on question asking whether "a promise that $M$ halts in time $\le n^c$" isn't precisely the restriction $M\in P$?  Also a reminder of the  proviso that for fixed $n$, we are to upper-bound the runtime of $M$ using $n$-polynomial resources ... because otherwise we might just as well do an exhaustive sampling of runtimes for EXP-many inputs.   Hopefully this comment is formatted OK.  
> **username_3**: @Jukka: With this formulation it seems to me one gets an undecidable problem. @username_0: It seems you are also interested in a *specific* input length as well?  
> **username_4**: Reading the question on MathOverflow, I think that you are asking the following.  For a Turing machine M and an integer n≥0, let f(M,n) be the maximum number of steps required for M to halt on the input x over the strings x∈{0,1}^n.  The question I believe you are asking here is whether there exists a polynomial-time Turing machine M such that computing f(M,n) requires time exponential in n.  (Note that M is not part of the input.)  
> **username_0**: Yes, to the best of my (not-expert) understanding, that is *exactly* the question intended.  Thank you very much for stating it so clearly!  
> **username_2**: @John: Please edit the question so that it reflects exactly what you want to know.  
> **username_2**: @Tsuyoshi: I got the impression that we are looking for upper bounds, not exact running times. And if you fix $M$, and you know that $M$ halts in polynomial time, then computing an upper bound on $f(M,n)$ is easy. (Easy in the sense that an efficient algorithm exists; designing the algorithm for a given $M$ is another question.)  
> **username_0**: Jukka, anticipating your request, I have just now edited the question to embrace username_4's formulation of it.  
> **username_4**: @Jukka: I agree that computing an _upper bound_ on f(M,n) is trivial for every fixed poly-time Turing machine M.  What I wrote in the comment was the best guess that I could come up with, though.  
> **username_0**: @Jukka: "And if you fix M, and you know that M halts in polynomial time, then computing an upper bound on f(M,n) is easy. (Easy in the sense that an efficient algorithm exists; designing the algorithm for a given M is another question.)" ... Hmmm ... so if I set (for example) n=10^4, and set M = (an Python script, oracularly guaranteed to be in P, but otherwise undocumented) ... you can efficiently upper-bound f(M,n)? ... if so, please post this marvelous algorithm as an answer!  
> **username_4**: @John: What Jukka said is that you can construct countably many efficient algorithms such that at least one of them gives you a correct upper bound on f(M,n) for all n.  Namely, the k-th algorithm just outputs n^k+k.  Then the promise that M is poly-time implies that there is a single k such that the k-th algorithm outputs a correct upper bound on f(M,n) for all n.  As he wrote, finding a correct k is a separate matter.  See also a [similar example](http://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2825#2825).  
> **username_0**: Aha!  This is precisely the insight that I was seeking ... an algorithm exists that is correct and efficient ... but there is no efficient means---even in principle?---of validly and verifiably selecting it from an (exponentially large) set of incorrect algorithms.  I will sleep on this insight tonight ... it appears that much depends on whether validation and verification is accounted as a computational cost.  Truly, P is a tricky complexity class.  Thank you!  

---

## 2 answers

### Answer by username_6 on 2011-02-03. Score: 16 | Accepted answer

As currently asked, the answer to the question is yes, assuming that there are problems in NE (non-deterministic time $2^{O(n)}$) that require doubly-exponential time to be solved. Under the standard assumption that, $NE\neq E$, there is a turing machine $M$ such that computation of $f(M,n)$ given $n$ cannot be done in time polynomial in $n$.

In general, suppose that there is a language $L$ that is in NE, and that cannot be solved in deterministic time $t(2^n)$ (plausibly, there could be such a language with $t(n) = 2^{n^\epsilon}$). Let $L'$ be the language that contains only the strings of the form $1^N$ such that the $N$-th string in lexicographic order is in $L$. Thus $L'$ is in NP and such that if $1^N \in L'$ then it has a certificate of length $\leq N$, but such that $L'$ cannot be solved in deterministic time less than $t(N)$.

Define the polynomial-time turing machine $M$ so that, on input $x$ of length $N$, it decides whether $x$ is a witness for $1^N$. If it is a witness, then $M$ accepts in time, say $N^2$, otherwise it keeps going some more, and rejects after $N^3$ steps. So we see that $f(M,N)= N^2$ if $1^N \in L'$, and $f(M,N) = N^3$ otherwise, and so computing $f(M,N)$ cannot be done in time less than $t(N)$


---

### Answer by username_5 on 2011-02-02. Score: 7

[Upon reading more of the comments on the question, I realized that this answers Jukka's second formulation, but the original question was actually more about Jukka's first formulation. I'll leave this answer and the comments here for discussion for a while.]

The problem you are trying to solve (as formalized by Jukka's second comment above) is not computable, and so in particular does not have an EXP upper bound (proof below).

You might also be interested in Chapter 6 of Juris Hartmanis' book "Feasible Computations and Provable Complexity Properties" which discusses the difference between the collection of languages decidable in a given time bound, and the collection of languages *provably* decidable in that time bound.

*Proof:* Intuitively the idea is that, any algorithm $A$ can only look at finitely much data before deciding the runtime of $M$. So we can construct an $M$ for which the finite amount of data that $A$ looks at is not enough to decide even an upper bound on the runtime of $M$.

Formally, suppose there were some algorithm $A$ which, given the description of a Turing machine $M$ as input, with the promise that $M$ runs in time $n^c$ for some unknown constant $c$, outputs a $k$ such that $M$ runs in times at most $n^k$ (i.e., $c \leq k$). (Note that this is a promise problem: if $M$ describes a Turing machine which does not run in polynomial time, we do not care what $A$ outputs, or even if $A$ halts.)

Then $A$ fails on a description the following machine $M\_0$. Let $n\_0$ be the length of a known description $D$ of $M\_0$. On input $0^n$, $M\_0$ starts trying to compute $A(D)$. If it takes more than $n$ steps, $M\_0$ halts. Otherwise, $M\_0$ gets the output $k = A(D)$. $M\_0$ then loops for $n^{k+1}$ steps and halts. $M\_0$ runs in polynomial time and so satisfies the promise, yet $A(D)$ outputs a $k$ such that $n^k$ is *not* an upper bound on the runtime of $M\_0$.

> **Comments:**
> **username_0**: Hmmmm ... Joshua, your answer seemingly implies that the question that started this whole sequence, namely, "Does BPQ^P = BAP?", or equivalently, "Is P low for BQP?", is still open ... because (as your answer implies) there is in general no P-uniform reduction of the oracular P in BQP^P to the reversible logic gates that are essential to the usual reduction methods.   You may well be right ... but this is AFAICT *not* the [consensus view](http://rjlipton.wordpress.com/2011/01/25/factoring-is-in-bqp/#comment-10471).  So, please post more! :)  
> **username_0**: Hmmmm ... again ... Joshua, your answer is a good start ... but there are two concerns: (1) the run-time estimation problem surely *is* computable (for every n) by the inefficient expedient of observing the runtime for all possible, and (2) assuming that your proof can be fixed-up to show that run-time estimation is *not* in P (which is my intuition too) the question's second half is still open, namely, concretely exhibit an algorithm in P whose runtime is harder-than-P to estimate.  Despite these concerns, your reply is a wonderful start ... eventually I hope to rate it as an "answer".  :)  
> **username_0**: LOL ... Joshua, one final note ... I see you are at UChicago ... where my wife, my son and I all attended ... so please let me say, our whole family sympathizes with the horrendous winter weather that you are facing today! :)  More to the point, my thinking along P-centric lines was first stimulated, not only by practical challenges in quantum systems engineering, but also by a marvelous lecture by Ketan Mulmuley, whose theme was "The mysterious complexity class P". So good luck with a Chicago-style blizzard *and* with the mysteries of P.  :)  
> **username_5**: I think I understand now. My answer was to Jukka's *second* formulation of your question, which I stand by; I also agree with the consensus view. Based on your most recent comment, I think Jukka's *first* formulation is more what you are asking about, which I'll have to think more about. Oh, and upon reading further comments I see Kristoffer already anticipated what I said. I think it would be helpful if you added Jukka's first formulation to the question statement for clarification. Thanks for the well-wishes.  
> **username_0**: It seemed to me that username_4's formulation best captured the intent of my original question ... and was reasonably consonant with everyone else' formulation ... and most important of all, was likely to stimulate good answers ... and so I have edited the question to ask for responses specifically to Tsuyoshi's formulation.  Thanks!  

---

