What Is P

Links to this page
Edit this page
Entry portal
Advice For New Users

Prev: Time Complexity / Next: What is NP?
So we have the idea of

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.
Some problems are trivial to solve. For some problems an instance that's k times bigger just takes k times longer. Some problems are barely more difficult. Long multiplication, for example, goes up as the product of the number of bits in each multiplicand. The obvious algorithm for multiplying matrices is bounded by a cubic function of the sizes. And so on.

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.

Prev: Time Complexity / Next: What is NP?
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout