Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.lang.javascript Subject: Re: Update only if not already in array Date: Sat, 04 Mar 2017 20:56:43 +0000 Organization: A noiseless patient Spider Lines: 66 Message-ID: <87efyckbg4.fsf@bsb.me.uk> References:

<567cadf8-91e1-4e1d-9183-09b60658ec39@googlegroups.com> <72c9bb07-427c-4256-bc82-0b0a3acd6cc5@googlegroups.com> <8e90e371-950e-4774-89f4-1c54566745fa@googlegroups.com> <20ca53b3-e664-4d34-86ec-1bc0e5fb4b1e@googlegroups.com> <87o9xhjb00.fsf@bsb.me.uk> <8fae31a5-24ba-46ac-a746-299a4eb57671@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="be76830f0dbbc00b80e00937aa6fd11d"; logging-data="28215"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1845NsmHtO5oLVEY2278rJbo07ctDNnGcA=" Cancel-Lock: sha1:qMgj6wbCNRLNAX7hvPVx8baMQD8= sha1:hybeEvIXlVP+qoMvEqtsPbGC+gc= X-BSB-Auth: 1.d73e72ffd88211cb7b68.20170304205643GMT.87efyckbg4.fsf@bsb.me.uk Xref: csiph.com comp.lang.javascript:32681 "Michael Haufe (TNO)" writes: > Ben Bacarisse wrote: > >> NP-hard is precisely defined, but would you say that when someone talks >> about a hard problem they always mean NP-hard? I suppose that's the >> natural thing to assume when talking about complexity but I wouldn't be >> certain. It still carries a strong informal meaning. > > Of course in general conversation, no. Nor in general conversation > about programming. Most programmers and developers have no formal > education and therefore carry their own bias with their > terminology. Confusion is caused when the same word is used with > different meanings by people in the same topic being discussed and > should be avoided. When Jonas moved from informal conversation to > criticism regarding factorization he moved into a field where the > terminology is is not so informal. > > In most writings IME, a "small" problem is computable in polynomial > time (such as n^3). Whereas a "large" problem would be computable in > exponential time (such as 2^n). That's interesting. I've not come across that usage. I would take the terms small and large to refer to the quantity of data. > For example: > > If I had two functions, each with a respective running time of the above: > > // O(n^3) > function small(n){ ... } > > // O(2^n) > function big(n){ ... } I wanted to mention a pet peeve of mine, but I see from Wikipedia that it's becoming accepted to use O(f) in this way. But in case there is some chance save the old meaning, I'll just say that when I leaned about it, Big-O was only an (asymptotic) upper bound, so the function called small is also O(2^n), and the one called big might be O(n^3). (A lower bound was given by Omega and both bounds by Theta.) > small(1000) // 1 billion steps to complete > big(1000) // 1 x 10^301 steps to complete Or almost any other number of steps, surely? The order of growth says only that steps(small(2*x)) ~ 8*steps(small(x)). >> Anyway, if we take hard to mean NP-hard then integer factorisation is >> not know to be hard, and most people would say that they don't expect it >> to turn out to be. The key new fact being that we now know that >> primality testing is in P which puts the decision problem version of >> factorisation in co-NP. > > Factorization is considered "hard" or "difficult" presently [3] > because you have to use brute force to search for possible solutions > instead of deriving them directly from what was computed already That's probably how Jonas meant it, too. Was your complaint that he should have put "hard" in scare quotes rather than "thought"? If so, I misunderstood your original reply. Sorry about that. -- Ben.