Talk:Pseudo-polynomial time

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Mid	This article has been rated as Mid-priority on the project's priority scale.

Systems Mid‑importance

	Systems science portal This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.SystemsWikipedia:WikiProject SystemsTemplate:WikiProject SystemsSystems articles
Mid	This article has been rated as Mid-importance on the project's importance scale.
	This article is within the field of Operations research.

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)[reply]

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)[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

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

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

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)[reply]

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