Complexity theory: Complexity zoo

Wel­come, vis­i­tor! Get ready to ex­er­cise your sense of won­der and ex­pand your mind on the zoo of com­plex­ity.

That where are the cages of the an­i­mals, you ask? No cage could con­tain our spec­i­mens, I must say. But you can get a glimpse of their na­ture through the chalky defi­ni­tions in each of those black­boards. Where shall we go first?

Oh yes! \(P\), the class of prob­lems solv­able in polyno­mial time. A pop­u­lar crea­ture in our in­stal­la­tions. It is com­monly ac­cepted that this class en­com­passes the prob­lems which can be solved effi­ciently. Now, bear in mind that the classes in this zoo only clas­sify prob­lems at­tend­ing to how fast the com­pu­ta­tional power you need to solve them grows com­pared to the size of the prob­lem you are solv­ing! That means, even if all grow at the same polyno­mial pace, some of the prob­lems who lurk in­side this class need a huge over­load of re­sources from the very be­gin­ning, which makes them in­tractable! Not to talk about the mul­ti­plica­tive fac­tor, which also gets ig­nored in mak­ing this dis­tinc­tion be­tween classes, or the de­gree of the polyno­mial which up­per bounds the func­tion! Beliefs like that \(x\) grows as fast as \(1000 x^{42}+10^{100}\) can be mis­lead­ing if not prop­erly un­der­stood.

How­ever, in prac­tice such in­stances are rare, and \(P\) is still used thor­ough all com­puter sci­ence as a syn­onym of effi­ciency—though they pay spe­cial at­ten­tion to the de­gree and dis­t­in­guish be­tween func­tions in \(\mathcal{O}(n)\) and func­tions in \(\mathcal{O}(n*log(n))\), even though all pro­grams as­so­ci­ated fall within \(P\).

The next crea­ture is with­out a doubt the most fa­mous of the zoo! Meet \(NP\), the class of prob­lems whose solu­tion are eas­ily check­able. This lit­tle crea­ture is the re­spon­si­ble of mod­ern cryp­tog­ra­phy, which re­lies on func­tions easy to com­pute but hard to in­vert.

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

An­nouncer: Ladies, gen­tle­men and chil­dren who are to­day with us! We pre­sent to you the main at­trac­tion of our bes­tiary, the in­fa­mous \(P\) vs \(NP\)!

An­nouncer: You may already have seen both of those crea­tures, but are they two differ­ent beasts? Or only two as­pects of the same thing?

An­nouncer: Look again at them, and re­al­ize. If find­ing a solu­tion to a prob­lem is easy, then check­ing whether a given solu­tion is true is also easy! You can always just find the solu­tion again from scratch and check that both co­in­cide. So we con­clude that \(P\subset NP\). Can the re­verse in­clu­sion be true as well?

An­nouncer: Imag­ine for a mo­ment! The hard prob­lems of cre­ativity, solved at once through the clever ap­pli­ca­tion of an effi­cient al­gorithm! Au­to­mated short proof writ­ing! In­stant re­ver­sal of one way func­tions!

An­nouncer: How­ever, we sus­pect that they are differ­ent, though a proof has re­mained elu­sive through the years.

(the pub­lic cries: If we have been search­ing for decades for such a proof and none has been found then you should re­vise your be­liefs and up­date against that! Why sus­pect oth­er­wise?)

An­nouncer: We seem to have an ex­cep­tion­ally well ed­u­cated au­di­ence to­day! Then again, we have been also on the search for a proof of the op­po­site with­out fruition. Why give this fact more weight in the Bayesian scheme of the things? There hap­pens to be a some­what con­voluted rea­son for this. For if \(P=NP\), then we would ex­pect proofs to be eas­ier to find, while if \(P!=NP\) the op­po­site is true! So it only makes sense that is more prob­a­ble that we live in the world where \(P!=NP\)noteFor a for­mal­iza­tion of this no­tion check nat­u­ral proofs. Also, see Ar­gu­ments against \(P=NP\)!

An­nouncer: And that’s all for to­day, folks. Keep en­joy­ing your visit though the zoo!

(To be con­tinued)


  • Complexity theory

    Study of the com­pu­ta­tional re­sources needed to com­pute something