What Is P

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

• A problem is a collection of instances
• A "solution" to a problem is an algorithm that maps instances to solutions
• Given a solution, its Time Complexity is an upper bound for how long it takes

Rather than talking about multiplication it's easier to talk about squaring - the problems are roughly equivalent. Specifically,    so if we can square, we can multiply with just a little extra work.

This is overstating the case. If the polynomial in question is    for example, then you're in trouble anyway, but even so, "polynomial" is a reasonable line to draw.

In short, we regard a problem as "easy" if we know an algorithm whose time complexity is bounded by a polynomial function. Squaring a number, for example, takes time less than    for a number of    bits, for some constant    It can be done faster, but it's certainly bounded above by (and hence no worse than) a polynomial.

You can go see the page on Polynomial Time if you want more details, but you need to return here.

Any problem with a known algorithm whose performance is better than or equal to some polynomial is said to be in the complexity class P. Specifically, it has a Polynomial Time algorithm.

So P is the collection of all problems whose time complexity is bounded by a polynomial.