4
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ What do you mean by a "concrete algorithm"? Is it something realized by a single Turing machine? If so, then you are talking about a complexity of a problem which does not assume any input, and this does not make sense. $\endgroup$
    – Sergei Ivanov
    Commented Feb 2, 2011 at 21:32
  • $\begingroup$ Yes, by "concrete 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 such a hard-to-estimate code." $\endgroup$
    – John Sidles
    Commented Feb 2, 2011 at 22:07
  • 2
    $\begingroup$ By the way, your question, and my answer, do note affect the proof that $BQP^P = BQP$. In general, a complexity class cannot be used as an oracle, only a language can, so $BQP^P$ is shorthand for $\bigcup_{L \in P} BQP^L$. If a language $B$ is in $BQP^P$, it means that there is a fixed language $L$, with a fixed polynomial time algorithm $A$ of fixed polynomial running time $n^c$, such that $L$ can be solved by a $BQP$ algorithm with oracle access to $L$. This means that we know $A$, and we know an upper bound $n^c$ to its running time, we don't need to compute its running time to simulate $A$ $\endgroup$
    – Luca Trevisan
    Commented Feb 4, 2011 at 0:32
  • 2
    $\begingroup$ No, no, I am saying that if A exists and the upper bound n^c exists, then a simulation exists, which what statements about problems being in certain complexity classes mean. If A is known and the upper bound is known, then simulation is known. However, "known" is a mathematically undefined concept, the definitions (and hence the theorems that use the definitions) use existence. $\endgroup$
    – Luca Trevisan
    Commented Feb 4, 2011 at 17:37
  • 1
    $\begingroup$ (continuing because I exceeded length limit) In practice, if the premise of a theorem is given in a constructive form, you will get the conclusion constructively, and so the theorems are usable, but it's a category error to want a constructive conclusion from an existential premise $\endgroup$
    – Luca Trevisan
    Commented Feb 4, 2011 at 17:37

1 Answer 1

Reset to default
3
$\begingroup$

I'm not entirely sure I understand your question, but you may be interested in the Robertson-Seymour Theorem. It shows that any family of graphs satisfying a certain property (being "minor-closed") has an algorithm to test membership which runs in cubic time, but it does not actually give the algorithm. Or rather it gives the algorithm in terms of some finite amount of auxiliary data (the set of "forbidden minors") which could be enormous, yet is fixed for any given minor-closed family. That is to say, the constants in the asymptotic run time are not bounded explicitly and could be huge. I believe there has been some work showing that computing these forbidden minors, given certain types of descriptions of the family of graphs, is hard.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Over on TCS StackExchange, Luca Trevisan has <a href="cstheory.stackexchange.com/questions/4704/… an explicit construction</a> that (if I grasp it correctly) yields a class of algorithms in P for which runtime estimation is harder-than-P ... it will take me a few days to digest Luca's ideas, and their implications for the questions at-hand. $\endgroup$
    – John Sidles
    Commented Feb 3, 2011 at 14:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .