Most recent change of WhatIsP

Edit made on June 15, 2025 by DavidKutner at 17:14:48

Deleted text in red / Inserted text in green
WM
HEADERS_END
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

[[[>50 Rather than talking about multiplication
it's easier to talk about squaring - the problems
are roughly equivalent.
Specifically, EQN:ab=\frac{1}{4}\((a+b)^2-(a-b)^2\)
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.

[[[>50 This is overstating the case. If the
polynomial in question is EQN:n^{1000}, for
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 EQN:an^2 for a number
of EQN:n bits, for some constant EQN:a. It can be
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.

[[[>50 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?