Jump to content

Polynomial time reduction


Jospeh K

Recommended Posts

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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 by SarK0Y
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.