Editing WhatIsP
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Apr 25 23:46:26 2024.
Press
to finish editing.
Who can edit this page?
The World
Members
Council
Admin
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\) 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 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 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?