Hi! You came back? Great! That means that you haven’t had enough complexity yet!
Today, let’s explore what P and NP problems are, and how this impacts the resolution of problems.
Complexity of a problem
As we saw last week, the complexity of an algorithm includes a connotation of « worst case », because it measures the « maximum » number of elementary operations that are needed for its execution.
Some problems are more difficult to solve than others, in the sense that they require more complex algorithms to be solved.
With this in mind, a problem is said to be « polynomial » if it can be solved by an algorithm whose complexity is asymptotically dominated by a polynomial.
For other problems, it’s more difficult to determine their complexity class. This is the case for the TSP, for example. No one’s managed to find a polynomial algorithm to solve it, and there are strong suspicions that this is just not possible.
Without going into too much detail, we often need to use algorithms with an exponential complexity to solve NP problems.
You would just have to rewrite the input and reinterpret the output to adapt it to the new problem. These rewrites can be done using polynomial algorithms.
So, today I’ve shown you that if you are able to solve the TSP, you are also able to solve any other NP problem. From a theoretical point of view this sounds nice, but from an operational point of view, solving the TSP still requires an exponential algorithm, which for our maze game is probably not ideal. Don’t let this get you down, because next week we’ll show you how to solve the problem faster, provided that you agree that the solution is not necessarily the optimal one, but a good enough one.
Complexity in space
The classes of complexity above describe the time requirements to solve problems. In order to measure other requirements, such as memory consumption, there exist other classes of complexity.
Similar to time complexity, space complexity measures the smallest amount of memory a program would need to solve the problem in consideration, for the worst-case input. Again, it can be seen as a « minimum of maximum ».
We also use big-O notations to describe the memory usage, as a function of the input size. As examples, denotes linear memory usage, and indicates solving the problem requires at least a quantity of memory that grows factorially with the dimension of the input.
As for time complexity classes, there is a huge taxonomy of space complexity classes.
Among the classic ones, PSPACE indicates that a problem cannot be solved with less than a polynomial amount of memory.
Space and time complexities are not unrelated. As an example, it is shown that NP ⊆ PSPACE. Still, there are numerous equalities between classes that are unknown, many of which have been open problems in research for decades.