Update #6:

Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer *Are runtime bounds in P decidable? Answer: No*.

Emanuele's answer illuminates (for me) Luca Trevisan's answer Do runtimes for P require exp resources to upper-bound? Answer: yes.

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, which in aggregate I regard as an answer to the question posed (and I have modified the title to reflect this).

Update #5:

I am pleased to report slow-but-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?*

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

Update #4

Rather slowly, an answer is crystallizing both here and in a parallel discussion on TCS StackExchange.

At the present rate of progress there is reason to hope that before the end of February there will be a summary answer that is technically correct, reasonably comprehensive, solidly referenced ... and fun to read too. In the meantime, the short answer is (AFAICT) "yes" and "yes".

If you think that you already know the longer answer ... then please don't wait on me or anyone else, to post it.

Update #3:

To appreciate why it may take awhile for a concluding summary answer to appear, please see Luca Trevisan's comment (below) that begins "By the way, your question, and my answer, do not affect the proof that $BQP^P=BQP$ ..." (and also my response).

Informally, the accepted usages and proof methods of complexity theory sometimes appear to engineers as what Dick Lipton and Ken Regan, on their weblog *Gödel's Lost Letter and P-NP*, have called "Flaming Arrows".

By "flaming arrow" is meant, a piece of proof machinery that causes the reader to exclaim “Are they allowed to do that?”

By engineering standards, the machinery of complexity theory contains multiple flaming-arrow elements ... in particular, cross-disciplinary discrepancies in the accounting of computational costs associated to verification and validation processes take awhile to grasp.

Thank you all for your patience, and thanks go to Luca Trevisan, especially, for his comments.

Update #2:

Over on *TCS StackExchange*, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is the same as the one asked here, "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

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 here on on *MathOverflow*, that question being, "Does BQP^P = BQP? ... and what proof machinery is available?", which in turn generalized 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?"

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, and will post that summary both here and on *TCS StackExchange*.

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

Update #1:

On TCS Stackexchange, Chicago's Joshua Grochow has suggested (provisional) answers that amount to "yes" (EXP resources are required) and "no" (no concrete instance given as yet). There are still several technical issues to be addressed (these issues reflect mainly my slow imperfect understanding), and I will post a summary when the dust settles. My thanks as always go to all who so kindly and generously contribute to these forums.

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

The practical motivation for this question arises from a previous MathOverflow question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" (to which Aram Harrow supplied the answer "yes", accompanied by good references). The present question asks about the computational resources that are required to accomplish this reduction.

As before, *P* is the standard complexity class that is associated to polynomial-time algorithms implemented on (classical) Turing machines, and *BQP* is the standard (quantum) complexity class *Bounded Error Quantum Polynomial Time*. We have specifically in mind a logic-gate instantiation of *BQP*, and for *P* we have in mind a single-tape Turing machine.

Thus in practical terms, the question concerns the generic computational complexity of converting a Turing algorithm (stipulated to be in *P*) to a circuit representation.

The number of gates in the circuit provides a *prima facie* upper bound (hmmmm ... within a coefficient?) for the runtime of *P*, and for any given input length $n$ this gate-number can always be upper-bounded as the maximum over an exhaustive sample of $2^n$ inputs.

The following questions then are natural. Are there algorithms in *P* whose runtime estimation provably requires a survey of runtimes for exponentially many inputs? If so, are concrete examples of such hard-to-runtime-estimate algorithms known? Or is the converse true ... every algorithm in *P* has a runtime that can be upper-bounded by an algorithm that also is in *P*? If so, what is that runtime estimation algorithm?

These algorithm-to-circuit conversions have considerable practical interest for engineers, and so my appreciation and thanks go to all the mathematicians who contribute to this fine site.

For me, the most enjoyable answer would be a concrete algorithm in *P*, whose runtime estimate requires more-than-*P* resources to upper-bound ... it would be fun just to contemplate such an algorithm. Of course, it would be similarly fun, to appreciate that *P* contains no such algorithms ... and mysteriously fun to discover that such algorithms provably exist in *P*, and yet no concrete example can be exhibited ... and so I am greatly looking forward to any and all answers.

Once this runtime estimation question is answered, I will incorporate it into a summary answer for the previous question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" ... along with my thanks to all who answer.

existsand the upper bound n^cexists, then a simulationexists, which what statements about problems being in certain complexity classes mean. If A isknownand the upper bound is known, then simulation isknown. However, "known" is a mathematically undefined concept, the definitions (and hence the theorems that use the definitions) use existence. $\endgroup$ – Luca Trevisan Feb 4 '11 at 17:373more comments