# What Is P

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

• 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,  $ab=\frac{1}{4}$$(a+b)^2-(a-b)^2$$$  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  $n^{1000},$  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  $an^2$  for a number of  $n$  bits, for some constant  $a.$  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?