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

Current License: CC BY-SA 2.5

21 events

when toggle format	what		by	license	comment
Apr 13, 2017 at 12:58	history	edited	CommunityBot		replaced http://mathoverflow.net/ with https://mathoverflow.net/
Apr 13, 2017 at 12:32	history	edited	CommunityBot		replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Feb 18, 2011 at 18:16	history	edited	John Sidles	CC BY-SA 2.5	Modify title to reflect answer
Feb 18, 2011 at 18:09	history	edited	John Sidles	CC BY-SA 2.5	Progress #6; Post Made Community Wiki
Feb 18, 2011 at 17:16	history	edited	John Sidles	CC BY-SA 2.5	Progress update #5
Feb 8, 2011 at 21:55	history	edited	John Sidles	CC BY-SA 2.5	progress update
Feb 4, 2011 at 18:50	comment	added	John Sidles		LOL ... I too am having trouble with the idioms of comment mark-up. The above link was intended to be "faculty.washington.edu/sidles/Litotica_reading/BQP_exists.jpg"... a picture of the concrete meaning that engineers associate to "construction." More broadly, it's not easy---for TCS non-specialists especially---to assess whether the reduction BQP^P to P is constructive or not ... it is my hope that eventually the MathOverflow/TCS StackExchange discussions will yield in a clearly-stated explanation of this point, which has appreciable practical importance.
Feb 4, 2011 at 18:42	comment	added	John Sidles		Luca, thank you yet again. Once I appreciate what complexity theorists mean by the "existence" of algorithms/circuits (mainly by working through Arora and Barak's text), then I hope and expect to grasp your comments in-depth ... and look forward to this very much. And yet, I have to respect too what engineers conceive when an algorithm/circuit is said to "exist", which very roughly is "<a href="faculty.washington.edu/sidles/Litotica_reading/…! Let's read the blueprints and order parts</a>!" ... the "reduction of BQP^P to BQP" is very different in these two cases.
Feb 4, 2011 at 17:37	comment	added	Luca Trevisan		(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
Feb 4, 2011 at 17:37	comment	added	Luca Trevisan		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.
Feb 4, 2011 at 16:34	history	edited	John Sidles	CC BY-SA 2.5	Luca Trevisan comment ... LaTeX typo corrected
Feb 4, 2011 at 16:05	history	edited	John Sidles	CC BY-SA 2.5	progress update #3
Feb 4, 2011 at 15:23	comment	added	John Sidles		Thank you for this comment ... I am slowly working through chs. 1,2, and 6 of Arora and Barak's "Computational Complexity: A Modern Approach" to appreciate the (many) fine points implicit in it. For engineers, it is natural to extend your comment's final sentence to read: "We know $A$, and we know an upper bound $n^c$ [exists] to its runtime [for unknown $c$], [but] we don't need to compute its runtime to simulate $A$ in a concrete circuit model." Hmmm ... but then the gate-count tells us $c$ ... which we thought was hard to compute ... it is taking awhile to parse these subtleties! :)
Feb 4, 2011 at 0:32	comment	added	Luca Trevisan		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$
Feb 3, 2011 at 14:26	history	edited	John Sidles	CC BY-SA 2.5	Luca Trevisan answer accepted on TCS StackExchange
Feb 3, 2011 at 3:28	answer	added	Noah Stein		timeline score: 3
Feb 3, 2011 at 0:36	history	edited	John Sidles	CC BY-SA 2.5	Link to Joshua Grochow's provisional answer
Feb 2, 2011 at 22:07	comment	added	John Sidles		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."
Feb 2, 2011 at 21:32	comment	added	Sergei Ivanov		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.
Feb 2, 2011 at 19:27	history	edited	John Sidles	CC BY-SA 2.5	"circuit depth" replaced by "number of gates"
Feb 2, 2011 at 18:50	history	asked	John Sidles	CC BY-SA 2.5

toggle format