Talk:Polynomial time
From Wikipedia, the free encyclopedia
| WikiProject Mathematics (Rated Start-Class) | ||||||
|---|---|---|---|---|---|---|
 |
||||||
| Mathematics rating: | Start Class | High Priority | Field: Discrete mathematics | |||
|
||||||
The mathematical expression is algebraic as opposed to transcendental, rather than polynomial as opposed to superpolynomial. Bo Jacoby 10:41, 6 March 2006 (UTC)
- algebraic vs. transcendental is a different distinction to polynomial vs superpolynomial. --Taejo|대조 18:27, 11 September 2008 (UTC)
Some texts use the term weakly polynomial run time. This means that run time is polynomial not in the size of the input, but in the numerical value of the input, which may be exponentially larger.
Could someone please clarify what this means? What may be exponentially larger? The quantity of input values to process? 72.83.244.154 (talk) 05:55, 30 December 2008 (UTC)
No, it is the numerical value of the input that can be exponentially larger than the size of its (e.g., binary) representation. Amending the sentence to make it clearer. 115.129.27.166 (talk) 08:09, 16 March 2009 (UTC)
strongly polynomial time means that the algorithm's running time is independent of the numerical data size
This is false: the size of an input, and hence the running time, does of course depend (logarithmically) on its numerical value, which is what is presumably meant by "numerical data size". Trying to find a better formulation. 115.129.27.166 (talk) 08:09, 16 March 2009 (UTC)
[edit] "[solvable in] polynomial time"?
My understanding of this subject matter is fuzzy at best, so I'm hesitant to be bold, but shouldn't it be "An algorithm is said to be [solvable in] polynomial time" or something similar? In recreationally reading up on P and NP, I've never heard anyone say that an algorithm IS polynomial time. 65.17.16.48 (talk) 17:44, 3 June 2009 (UTC)
- It is common to just say it's a polynomial time algorithm. Verbal chat 17:49, 3 June 2009 (UTC)
- Oh, that makes sense. The phrasing still sounds a little weird to me—but then again, the whole subject is a lot weird to me, so maybe that's not a problem. Thanks. 65.17.16.48 (talk) 18:00, 3 June 2009 (UTC)
