6

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.

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.

Community
  • 1
John Sidles
  • 1,536
  • 1
  • 12
  • 28
  • 2
    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 Feb 02 '11 at 22:04
  • 6
    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 02 '11 at 22:05
  • 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 n-bit inputs always terminates in n-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 Feb 02 '11 at 22:40
  • 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 Feb 02 '11 at 22:53
  • 5
    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 02 '11 at 22:59
  • To the best of my (imprecise) grasp of the language of complexity theory, that is precisely what I am asking .. thank you! :) – John Sidles Feb 02 '11 at 23:01
  • 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 Feb 02 '11 at 23:11
  • 3
    @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 02 '11 at 23:25
  • 5
    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 03 '11 at 00:36
  • 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 Feb 03 '11 at 00:54
  • 5
    @John: Please edit the question so that it reflects exactly what you want to know. – Jukka Suomela Feb 03 '11 at 01:19
  • 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.) – Jukka Suomela Feb 03 '11 at 01:22
  • Jukka, anticipating your request, I have just now edited the question to embrace Tsuyoshi Ito's formulation of it. – John Sidles Feb 03 '11 at 01:35
  • @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 Feb 03 '11 at 01:48
  • @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 Feb 03 '11 at 02:03
  • 3
    @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. – Tsuyoshi Ito Feb 03 '11 at 02:17
  • 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 Feb 03 '11 at 02:27

2 Answers2

16

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

Luca Trevisan
  • 4,912
  • 28
  • 34
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$.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 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 02 '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 03 '11 at 00: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 03 '11 at 00:46
  • 1
    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 Feb 03 '11 at 01:07
  • 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 Feb 03 '11 at 01:58