Talk:Pseudo-polynomial time

Unconvinced by the claims about the complexity of addition

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)

Example: Knapsack problem

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)

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

Strongly NP-complete

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)

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

Arithmetic

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)

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)

Numerical algorithm

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

Primality testing revisited

I came to this talk page for the same reason as the above. The naive primality test is checking $\scriptstyle \{2,3,...,n-1\}$, requiring $\scriptstyle n-2$ divisions. If you want to somewhat de-naivify that algorithm, you will halt at $\scriptstyle \lfloor {\sqrt {n}}\rfloor$, requiring $\scriptstyle \lfloor {\sqrt {n}}\rfloor -1$ divisions. Halting at any other number $\scriptstyle k$ with $\scriptstyle \lfloor {\sqrt {n}}\rfloor <k<n-1$, 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" ($\scriptstyle O({\sqrt {n}})\subset \mathrm {poly} (n)$, 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)

Confused by generalization

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)

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 (talk • contribs)