tag:blogger.com,1999:blog-3722233.post5817946159844596552..comments2020-02-27T07:10:16.369-05:00Comments on Computational Complexity: Six Questions about unnatrual and natural mathematical objectsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-75160779105099369002012-07-30T20:53:28.163-04:002012-07-30T20:53:28.163-04:00If we take "natural" to mean "is a ...If we take "natural" to mean "is a simple intuitive model of a phenomenon observed in nature", then I agree with Konstantin that brownian motion for 3. is as natural as anything.<br /><br />Or we can take natural to mean "the first construction that comes to mind works". Or at least that the construction does not feel like magic after one has seen it. I have a problem with evaluating that: once you have seen a technique it stops being magic (with the exception of some techniques I guess). For example, using brownian motion (as opposed to weierstrass) as an example of 3. to me is an infinite version of the natural argument, "if you want to construct a generic object, take a random one". In some sense being differentiable is highly non-generic property, and one expects to avoid it by somehow carefully sampling a random continuous function. But I cannot comment on the cantor set and devil's staircase. Both seem like obvious strategies once you realize the the set of real numbers is really a very big set. But natural..Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43261735621378792362012-07-30T20:43:35.438-04:002012-07-30T20:43:35.438-04:001. yes
2. no
3-6 yes.
My definition: If I can wri...1. yes<br />2. no<br />3-6 yes.<br /><br />My definition: If I can write a stochastic process that is nice and useful which has the property almost surely, then I have to go with it being natural.Dean Fosterhttps://www.blogger.com/profile/13906505132477512644noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90511581781628321202012-07-30T16:37:31.200-04:002012-07-30T16:37:31.200-04:001. Yes.
2. No.
3. Yes.
4. No.
5. Yes.
6. No
I'...1. Yes.<br />2. No.<br />3. Yes.<br />4. No.<br />5. Yes.<br />6. No<br /><br />I'm familiar with the pathological examples for 1,3,5 (I had in mind: Cantor, Weierstrass, and the Devil's staircase) - but I can't say either is very "natural" to me.Tom Gurhttps://www.blogger.com/profile/01207430976115238819noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52515527218589548932012-07-30T13:41:13.162-04:002012-07-30T13:41:13.162-04:00I'd say that the answer to #6 is yes. Just let...I'd say that the answer to #6 is yes. Just let r_n be a natural enumeration of the fractions in the interval (0,1). Define f(x) to be the sum of {1/n^2: x > r_n}. This isn't continuous, but it is strictly increasing, and seems natural to me. The proof that it has derivative zero almost everywhere is a fairly tasty exercise, and I'll leave it at that for now. It's not that hard to make a continuous example from this, but doing so obscures the differentiability argument.stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86139538268352596772012-07-30T13:37:16.483-04:002012-07-30T13:37:16.483-04:001-6: Yes (The Cantor set is quite natural. The Wie...1-6: Yes (The Cantor set is quite natural. The Wiener process is the most natural stochastic process :-) )Konstantinhttp://www.cs.princeton.edu/~kmakaryc/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16471327809207122622012-07-30T13:31:02.682-04:002012-07-30T13:31:02.682-04:00I think the answers are:
1. Yes.
2. Yes.
3. Yes. I...I think the answers are:<br />1. Yes.<br />2. Yes.<br />3. Yes. I remembered covering this in my analysis class.<br />4. No. The answer I had in mind for 3 doesn't work for 4.<br />5. Yes. Round down to the nearest member of the Cantor set.<br />6. #6 seems natural to me.Anonymoushttps://www.blogger.com/profile/10585945225477889921noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81087995543207082442012-07-30T10:32:42.033-04:002012-07-30T10:32:42.033-04:00Some spoilers are fine and some are not- which is ...Some spoilers are fine and some are not- which is why I <br />want people to post non-anonymously so if I block someone<br />I can email them why I blocked them.<br /><br />All will be clear tommorow.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39610995166717350582012-07-30T10:29:11.632-04:002012-07-30T10:29:11.632-04:00I'm not gonna touch the "natural" qu...I'm not gonna touch the "natural" questions with a 10 foot pole because matter of opinion of what you consider natural in these problems is an understatement.<br /><br />#3 and #5 are stereotypical trig trivia Qs.<br /><br />#3 is the definition of ye olde wiserstraus eqn (sorry almost surely misspelled his name) the point of which was an infinite summation of a bunch of cosine terms. Gut level believing it is pretty easy, proving is somewhat harder. Generally speaking doing calculus on infinite summations is often entertaining.<br /><br />#5 is ye old integral of trig functions trivia Q where you want a sine wave tilted so it never decreases and has a ridiculously high frequency so it hits zero deriv rather often in 0,1. One big problem with this design is "zero at almost every point" is arguably much different than has infinitely many zeros and unfortunately having infinitely MORE non-zeros than zeros in between the zeros. Many zeros vs high ratio of zeros vs non-zeros, so to speak. Also demanding [0,1] makes it harder to use a reciprocal in the trig function (to get infinitely many 0 derivs) than (0,1]. So its one of those superficially easy Qs that rapidly gets harder.<br /><br />I would assume question #1 is also a trivia question but I do not recall seeing it before. At least not at this time of morning.<br /><br />Trivia questions as in if you've seen the wiserstraus before you'll know the answer instantly, if not, well, then probably not. Also trivia in that I have no idea what to do with a wiserstraus other than confuse or hopefully interest people.Vince Mulhollonhttps://www.blogger.com/profile/07478615305937869074noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33103588242802723932012-07-30T10:20:09.932-04:002012-07-30T10:20:09.932-04:00Do you want spoilers?
1. Yes.
2. Yes.
3. Yes.
4. I...Do you want spoilers?<br />1. Yes.<br />2. Yes.<br />3. Yes.<br />4. I was going to say no, but then I decided yes.<br />5. On this one, I'm guessing that the answer must be no.<br />6. If 5 is actually yes, then this is absolutely no.joXnhttps://www.blogger.com/profile/09826430730393436145noreply@blogger.com