Problem complexity & NP-completeness

Reading time10 min

In brief

Article summary

Until now, we have studied the complexity of agorithms, as ways to estimate the required time needed to complete, as a function of its inputs. More generally, problems have a notion of complexity. This means that for a given problem, we cannot find an algorithm with better complexity to solve that problem.

Main takeaways

  • There are classes of complexities for problems.

  • The complexity of a problem describes the minimum complexity of an algorithm solving it.

  • There are intersections, inclusion relations, or equivalences between some classes of complexity.

  • Complexity can also describe the required memory to solve a problem.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Information

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

The complexity of a problem is related to the complexity of algorithms. The complexity of a problem is defined as the minimum complexity of the algorithms solving the 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.

Consequently, the complexity of a problem, which is intuitively the complexity of the "best" possible algorithm that can solve it, can be seen as a "minimum of a maximum".

Complexity classes

Some problems are more difficult to solve than others, in the sense that they require more complex algorithms to be solved.

As I will show you today, different complexity classes have been defined to describe how difficult it is to solve a problem.

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.

We've already encountered a lot of polynomial algorithms in this course, such as Dijkstra, or the BFS. So, if we consider, for example, the shortest path problems that these algorithms solve, they can be easily identified as being polynomial problems, because a polynomial algorithm solves them.

As a consequence, all these problems are in the complexity class called P, which stands for 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.

The TSP therefore belongs to a class of more difficult problems, called NP problems for "Nondeterministic Polynomial". Roughly speaking, a decision problem is an NP problem if we can check "quickly", with polynomial complexity, if a candidate solution is indeed a solution.

Without going into too much detail, we often need to use algorithms with an exponential complexity to solve NP problems.

Another famous class of problems is NP-Complete problems. NP-Complete problems are at least as difficult to solve as all other NP problems. In other words, an algorithm that can solve an NP-Complete problem can solve any other NP problem.

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.

As you might have guessed, it has been proved that the TSP is an NP-Complete problem.

Concluding words

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.

To go further

2 — 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, $O(n)$ denotes linear memory usage, and $O(n!)$ 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.

Some complexity classes and their inclusions (source).

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 $\subseteq$ PSPACE. Still, there are numerous equalities between classes that are unknown, many of which have been open problems in research for decades.

To go beyond

  • Complexity classes.

    A taxonomy of complexity classes of functions.

  • P = NP ?.

    The problem of determining if P and NP are the same is a major problem in computer science.