Talk:Pseudo-polynomial time
From Wikipedia, the free encyclopedia
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)
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)
