Talk:Polynomial time

Untitled

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)

I agree. Thanks for the contribution ylloh (talk) 14:15, 16 March 2009 (UTC)

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

You cannot "solve" an algorithm. You can solve a problem using an algorithm. What you probably want to say is that algorithm "runs" in polynomial time. Yet "is polynomial type" is also correct, here "polynomial type" is used as an adjective similar to "good" or "fast". —Preceding unsigned comment added by 128.97.82.220 (talk) 00:44, 11 September 2009 (UTC)

Problems with "strongly/weekly polynomial" section.

I see quite a number of problems with the present version of "Strongly and weakly polynomial time" section.

First, the definition (in the last paragraph) is quite vague. Does it refer to the "arithmetic model", and differs from "strongly polynomial" by requiring condition (1) but not (2) as defined in the second paragraph? If so, this should be stated explicitly. If the definition includes other models (e.g. Turing machines), then it is even less legible.

Second (assuming the above interpretation is correct) -- wouldn't having (2) but not (1) imply that all NP problems are "weakly polynomial"? I believe at least some NP-complete problems become polynomial if arbitrarily large numbers can be multiplied in a single step, right? If it is so, it should be mentioned (and maybe a better example than that in the third paragraph be given), and if not - the distinction explained.

Third, the statement "There are algorithms which runs in polynomial time in the Turing machine model but not in the arithmetic model" is confusing at best. Ideally, one should compare the algorithms for finding GCD for an arbitrary number of inputs on a Turing machine and in the arithmetic model -- and I believe there is no distinction then. Here we just artificially constraint such a general algorithm to the sub-part of it (the Euclidean algorithm). The definition of the "n goes to infinity" limit becomes meaningless, but it does not mean that the arithmetic model does NOT run in polynomial time (as the first sentence implies). It only means that the notion of "polynomial time" is undefined, because we artificially consider a sub-problem instead of a full problem. Note that "polynomial time" is undefined BOTH for the arithmetic model and for the Euclidean algorithm -- except that for the latter there is a SUB-DEFINITION, becoming meaningful for the sub-problem. If the size of a dollar bill in your wallet does not change, it does not mean that your salary does not change, right? "Constant-salary" and "constant-dollar-size" are just two different definitions.

Fourth, "algorithms which runs" has a typo. I'm not correcting it as I feel the whole paragraph should be removed or re-written. —Preceding unsigned comment added by 128.97.82.220 (talk) 01:50, 11 September 2009 (UTC)

As for the first two points let us restrict ourselves to decision problems. The class of all decision problems which can be solved in polynomial time on a Turing machine is P. For some of these problems there are strongly polynomial time algorithms. The other problems in P have weakly polynomial time algorithms. So "polynomial time" in the last paragraph means polynomial time on a Turing machine. Note that no NP-complete problem can be solved in weakly polynomial time, unless P = NP. (Any weakly polynomial time algorithm is a polynomial time algorithm, so such a result would imply that there is an NP-complete problem P.)

As for the third point, in the GCD problem used in the article the input consists of two integers, A and B. In the arithmetic model the size of such an input is 2, as there are two integers in the input. In the Turing machine model the size of the input is $\log A+\log B$ as this is the number of bits which is needed to represent A and B (in a binary encoding). One can show that one cannot compute GCDs in constant time in the arithmetic model (you need a constant time as any polynomial applied to 2 is a constant). It follows that the GCD problem cannot be solved in strongly polynomial time. The notion of "polynomial time" is certainly not undefined for this problem in any of the models.

I am afraid I don't see the typo in "An algorithm which runs". Frekui (talk) 11:05, 11 September 2009 (UTC)