Complexity theory: Complexity zoo

Welcome, visitor! Get ready to exercise your sense of wonder and expand your mind on the zoo of complexity.

That where are the cages of the animals, you ask? No cage could contain our specimens, I must say. But you can get a glimpse of their nature through the chalky definitions in each of those blackboards. Where shall we go first?

Oh yes! \(P\), the class of problems solvable in polynomial time. A popular creature in our installations. It is commonly accepted that this class encompasses the problems which can be solved efficiently. Now, bear in mind that the classes in this zoo only classify problems attending to how fast the computational power you need to solve them grows compared to the size of the problem you are solving! That means, even if all grow at the same polynomial pace, some of the problems who lurk inside this class need a huge overload of resources from the very beginning, which makes them intractable! Not to talk about the multiplicative factor, which also gets ignored in making this distinction between classes, or the degree of the polynomial which upper bounds the function! Beliefs like that \(x\) grows as fast as \(1000 x^{42}+10^{100}\) can be misleading if not properly understood.

However, in practice such instances are rare, and \(P\) is still used thorough all computer science as a synonym of efficiency—though they pay special attention to the degree and distinguish between functions in \(\mathcal{O}(n)\) and functions in \(\mathcal{O}(n*log(n))\), even though all programs associated fall within \(P\).

The next creature is without a doubt the most famous of the zoo! Meet \(NP\), the class of problems whose solution are easily checkable. This little creature is the responsible of modern cryptography, which relies on functions easy to compute but hard to invert.

\(NP\) also is the main star, together with \(P\), of one great show in the zoo. Oh, look! It is about to start!…

Announcer: Ladies, gentlemen and children who are today with us! We present to you the main attraction of our bestiary, the infamous \(P\) vs \(NP\)!

Announcer: You may already have seen both of those creatures, but are they two different beasts? Or only two aspects of the same thing?

Announcer: Look again at them, and realize. If finding a solution to a problem is easy, then checking whether a given solution is true is also easy! You can always just find the solution again from scratch and check that both coincide. So we conclude that \(P\subset NP\). Can the reverse inclusion be true as well?

Announcer: Imagine for a moment! The hard problems of creativity, solved at once through the clever application of an efficient algorithm! Automated short proof writing! Instant reversal of one way functions!

Announcer: However, we suspect that they are different, though a proof has remained elusive through the years.

(the public cries: If we have been searching for decades for such a proof and none has been found then you should revise your beliefs and update against that! Why suspect otherwise?)

Announcer: We seem to have an exceptionally well educated audience today! Then again, we have been also on the search for a proof of the opposite without fruition. Why give this fact more weight in the Bayesian scheme of the things? There happens to be a somewhat convoluted reason for this. For if \(P=NP\), then we would expect proofs to be easier to find, while if \(P!=NP\) the opposite is true! So it only makes sense that is more probable that we live in the world where \(P!=NP\)noteFor a formalization of this notion check natural proofs. Also, see Arguments against \(P=NP\)!

Announcer: And that’s all for today, folks. Keep enjoying your visit though the zoo!

(To be continued)