Polynomial time reduction

[Jospeh K]

Just in simple Terms... May be natural language.Could someone out there explain to me the meaning or intuition behind Polynomial time reduction. What exactly does it mean for a function to bounded by Polynomial time

Thanks

[2501]

I think MathWorld provides a simple explanation of Polynomial Time: http://mathworld.wolfram.com/PolynomialTime.html

 

Basically, it's just a statement about the ability of a particular algorithm of any complexity to solve a problem in a given amount of time. There are instances of a problem being too hard or taking too much time to solve; depending on the application it could be a good thing (for example, cryptography) or a bad thing.

[SarK0Y]

take really-living problems & you'll see 'flesh & blood' of such methodics. For instance, you have polynom of complex roots & you have algo to solve polynom of real roots. What could be done? Ye can represent P(x+i*y) ==F(x, y)+i*T(x, y). in other words, the(re) becomes:

 

T(x, y) == 0

F(x, y) == 0

====================

So, we make polynom w/ real roots, solve it & then turn real roots back to the complex form.

[Unity+]

I think MathWorld provides a simple explanation of Polynomial Time: http://mathworld.wolfram.com/PolynomialTime.html

 

Basically, it's just a statement about the ability of a particular algorithm of any complexity to solve a problem in a given amount of time. There are instances of a problem being too hard or taking too much time to solve; depending on the application it could be a good thing (for example, cryptography) or a bad thing.

It's less about time and more about the amount of steps required to get to the end of the algoithm

[SarK0Y]

It's less about time and more about the amount of steps required to get to the end of the algoithm

amount of steps can be easily converted to Time. actlually, (for each algo) we want to know how long it takes to resolve given problem at n width (width could mean number of elements, bits of precision).

[Unity+]

amount of steps can be easily converted to Time. actlually, (for each algo) we want to know how long it takes to resolve given problem at n width (width could mean number of elements, bits of precision).

It can be, but again time would be dependent on the processor quality. For example, a really bad processor would complete the task within 3n time while a really good one could complete it in 1/100*n time.

[SarK0Y]

It can be, but again time would be dependent on the processor quality. For example, a really bad processor would complete the task within 3n time while a really good one could complete it in 1/100*n time.

Actually, algo complexity (steps to resolve problem) is hardware dependent: you can have slower processor (in terms of freq.), but it could spin algo faster because of larger/better cache/memory/3OE(out-of-order execution). for instance, app gets fallen short on memory, then machine runs swaping & I/O becomes bottleneck the.

Edited November 4, 2014 by SarK0Y