Unconvinced by the claims about the complexity of addition

edit

I don't think addition is linear-time on a 1-tape Turing Machine.: to add an m-bit number to an n-bit number on a Turing machine you need to keep hunting back from one number to the other and this takes at least $mn$ steps. Bandanna (talk) 22:37, 24 July 2019 (UTC)Reply

Example: Knapsack problem

edit

I think that this article should mention the knapsack problem as an example of an NP-Complete problem with a pseudo-polynomial time algorithm.Truth Sifter (talk) 02:49, 14 March 2010 (UTC)Reply

Yes, i would like to see KNAPSACK explained here in more detail, aswell. --141.53.216.143 (talk) 19:28, 2 March 2013 (UTC)Reply

Strongly NP-complete

edit

Shouldn't there be cross reference between this and the page on Strongly NP-complete since they are two sides of the same coin? Houseofwealth (talk) 20:27, 26 February 2008 (UTC)Reply

Yes, there should. Please go ahead. --Mellum (talk) 12:14, 27 February 2008 (UTC)Reply

Arithmetic

edit

Changing "this algorithm performs up to n divisions" to "n/2 divisions" is fine (that's a slightly different algorithm, but still naive). Problem is, this immediately suggests "why doesn't the article mention that an even-better naive algorithm can stop at sqrt(n)?" Mentioning/explaining that seems even more of a digression; the page is already forced to include the paragraph that primality really "truly" polynomial, not just pseudo. ...Would it be better to abandon the problem of primality, and take some other example entirely?

(Separately: If we do stick with n/2, is it okay to omit the "floor" -- saying 'up to 3.5 divisions' strikes me as awkward.)

not-just-yeti (talk) 16:46, 28 February 2008 (UTC)Reply

I see your point. I can change it back to n, and mention that this a *very* naive algorithm. I don't believe there's anything wrong with the example itself Houseofwealth (talk) 17:16, 28 February 2008 (UTC)Reply

Numerical algorithm

edit

anonym: There is few mentionings of numeric algorithm, but there is not explained what is numeric problem or algorithm on wikipedia.

Primality testing revisited

edit

I came to this talk page for the same reason as the above. The naive primality test is checking  , requiring   divisions. If you want to somewhat de-naivify that algorithm, you will halt at  , requiring   divisions. Halting at any other number   with  , while obviously working, seems just to be the result of an unfinished thought. I would opt here for the first (very naive) algorithm, seeing how the square root might be confusing with the term "polynomial" ( , of course, but it could still be confusing), and also because it would get rid of the distracting floors. 85.226.204.10 (talk) 12:34, 1 September 2010 (UTC)Reply

Confused by generalization

edit

It is stated: "This makes numeric problems a special case by taking k to be the number of (binary) digits of the input." However the number of digits IS the size of the problem. Is not k the numerical value of the input? Please clarify, thanks. — Preceding unsigned comment added by 176.58.166.178 (talk) 10:32, 6 June 2012 (UTC)Reply

Indeed. (This is mostly how the book cited in the references does it as well, although it talks about problems containing multiple numbers, and takes k to be a MAX function of all the numbers in the input.) I changed it. 18:09, 23 April 2016 (UTC) — Preceding unsigned comment added by Vilhelm.s (talkcontribs)