tag:blogger.com,1999:blog-3722233.post112722326307479261..comments2020-07-09T17:10:19.118-04:00Comments on Computational Complexity: Short TakesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1127374763450301762005-09-22T03:39:00.000-04:002005-09-22T03:39:00.000-04:00The article of Lisa Randall has appeared in The Ne...The article of Lisa Randall has appeared in The New York Times rather than the Times.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127307890861553232005-09-21T09:04:00.000-04:002005-09-21T09:04:00.000-04:00Thanks. Fixed.Thanks. Fixed.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127281638130094242005-09-21T01:47:00.000-04:002005-09-21T01:47:00.000-04:00Shouldn't it be "principle" instead of "principal"...Shouldn't it be "principle" instead of "principal" ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127261671363964272005-09-20T20:14:00.000-04:002005-09-20T20:14:00.000-04:00nn <= (2*9-5 choose 9-2) = (13 choose 7) + 2 = 1718Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127257968316810682005-09-20T19:12:00.000-04:002005-09-20T19:12:00.000-04:00To answer Bram's comment, yes it does depend on th...To answer Bram's comment, yes it does depend on the old Erdos-Szekeres result (actually the result itself, rather than their version of it). I believe the range in Gerken's proof is that n > 500 and is less than 2000. Pavel Valtr has a simpler proof, but with a weaker bound.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127227193505083162005-09-20T10:39:00.000-04:002005-09-20T10:39:00.000-04:00It mentions requiring 9 points in convex position ...It mentions requiring 9 points in convex position (assuming I didn't misunderstand). Does this result dependon the other result that for any n a sufficient number of points on the plane will have n points in convex position? If so, what is the best known lower bound for n=9?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1127225906763870782005-09-20T10:18:00.000-04:002005-09-20T10:18:00.000-04:00Our number-one terminological misstep, in my view:...Our number-one terminological misstep, in my view: "NP". I have at least twice winced to see this misidentified (in print and by other scientists) with "non-polynomial time", i.e. with the entire gnarly mess *outside* P.<BR/><BR/>The situation is additionally bad because correcting that impression requires unpacking 'nondeterminism' for people--a fruitful notion, but much more conceptually difficult than the proof-checking or nonzero-acceptance-probability definitions of NP . I would've gone with 'PV' for 'polynomial verification'.<BR/><BR/>I also would've wanted to bring the more general, more comprehensible, and more a priori-significant 'lower bounds problem' into the forefront via better buzzwords. P vs NP takes pride of place among lower bound investigations, but (I would argue) this is by virtue of its discovered panoply of important complete problems, not because computer scientists are obsessed with pinpointing the power of a magical resource.Anonymousnoreply@blogger.com