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