# 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)

Parents:

• Complexity theory

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