# Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

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).

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?

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

Update #4:

As I work through the many fine comments—and Luca Trevisan'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 ... 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, Luca Trevisan has posted an interesting new comment relating to runtime estimation 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" Luca Trevisan's ingenious construction, 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).

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?"

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?"

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 Tsuyoshi Ito'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.

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.

• 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 Feb 2 '11 at 22:05
• 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 Feb 2 '11 at 22:59
• @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 Feb 2 '11 at 23:25
• 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 Feb 3 '11 at 0:36
• @John: Please edit the question so that it reflects exactly what you want to know. – Jukka Suomela Feb 3 '11 at 1:19

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)$

[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$.

• 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. So, please post more! :) – John Sidles Feb 2 '11 at 23:51
• 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 Feb 3 '11 at 0:23
• 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 Feb 3 '11 at 0:46