Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #32681
Show key headers only | View raw
"Michael Haufe (TNO)" <tno@thenewobjective.com> 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)).
<snip>
>> 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.
<snip>
--
Ben.
Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 05:36 -0800
Re: Update only if not already in array Julio Di Egidio <julio@diegidio.name> - 2017-03-01 05:53 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 07:29 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 12:04 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 02:27 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 13:02 +0100
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:07 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:13 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 18:20 +0100
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:30 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 23:41 +0100
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:48 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:52 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 00:07 +0100
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 16:00 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 12:35 +0100
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 06:00 -0800
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 15:24 +0100
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 07:02 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 15:51 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 09:57 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 20:56 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 15:30 -0800
Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 15:37 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:41 +0000
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:29 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-05 06:26 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 15:00 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-06 07:50 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 00:50 +0000
Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 06:46 +0100
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 11:23 +0000
Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 15:34 +0100
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 16:47 +0000
Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 17:55 +0100
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 17:28 +0000
Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 21:07 +0100
Re: Update only if not already in array Flippie Flink <flip@flink.not> - 2017-03-07 22:29 +0100
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-11 18:24 -0800
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-15 17:32 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-15 10:59 -0700
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 03:49 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-18 11:46 -0700
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:12 +0000
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:45 +0000
Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-26 11:54 -0700
Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-27 22:48 +0100
Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-01 15:32 +0100
csiph-web