From: xanthian@well.com (Kent Paul Dolan) Subject: Re: A new paper claiming P=NP Date: Wed, 11 Oct 2000 12:07:47 GMT Newsgroups: comp.theory,sci.math,sci.op-research,sci.crypt Summary: [missing] David C. Ullrich wrote: > Rajarshi Ray wrote: >> "David C. Ullrich" wrote: >> > On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray > >> > wrote: >>> [...] >>> >Is it not possible to implement the presented algorithm and try it >out >>> >on examples to see the growth rate, just as a preliminary check? >>> No. Suppose that a(n) is a sequence of integers and >>> a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n) >>> have polynomial growth? >> Well, I suppose it could be polynomially growing after 10^(10^10). Do >> you mean to say that empirical testing wouldn't reveal its polynomial >> behavior for n->oo, which is what we really mean by polynomial growth? > Yes. (And it's not just a theoretical thing: It happens all the >time that an algorithm that takes time O(n^2) is actually much >faster than one that takes time O(n).) There is a rather strong warning and object lesson against depending on the behavior in the first few ten to the ten to the ten test cases ;-) as a representation of asymptotic behavior found on the wonderfully (though possibly or not sarcastically) named "Law of Small Numbers" glossary page for the primes group; see: http://www.utm.edu/research/primes/glossary/LawOfSmall.html I keep this one around to toss at people to lazy to do the math and convinced that computer programs or math algorithms or whatever can be proved by exhaustive testing, a modern variant of black magic. Cheers! xanthian.