Complexity theory

Com­plex­ity the­ory is the study of the effi­ciency of al­gorithms with re­spect to sev­eral met­rics, usu­ally time and mem­ory us­age. Com­plex­ity the­o­rists aim to clas­sify differ­ent prob­lems into classes of difficulty and study the re­la­tions that hold be­tween the classes.

When study­ing com­putabil­ity, we are con­cerned with the iden­ti­fi­ca­tion of that which is or not com­putable in an ideal sense, with­out wor­ry­ing about time or mem­ory limi­ta­tions.

How­ever, of­ten in prac­tice we have to be more prag­matic. A pro­gram which takes a googol years to run is not go­ing to see much use. If you need more GbBytes to solve a com­pu­ta­tional prob­lem that atoms ex­ist in the uni­verse, you may as well go ahead and de­clare the prob­lem un­solv­able for all prac­ti­cal pur­poses.

Com­plex­ity the­ory raises the stan­dards of com­putabil­ity in draw­ing the bound­ary be­tween that which you can do with a com­puter and that which you can­not. It con­cerns the study of the asymp­totic be­hav­ior of pro­grams when fed in­puts of grow­ing size, in terms of the re­sources they con­sume. The kind of re­sources with which com­plex­ity the­o­rists work more of­ten are the time a pro­gram takes to finish and the high­est mem­ory us­age notethe mem­ory us­age is fre­quently called space com­plex­ity in any given point of the ex­e­cu­tion.

Com­plex­ity the­ory al­lows us to have a deeper un­der­stand­ing of what makes an al­gorithm effi­cient, which in turn al­lows us to de­velop bet­ter and faster al­gorithms. Sur­pris­ingly enough, it turns out that prov­ing that some com­pu­ta­tional prob­lems are hard to solve has in­cred­ibly im­por­tant prac­ti­cal ap­pli­ca­tions in cryp­tog­ra­phy.


The ab­stract frame­work in which we de­velop this the­ory are Tur­ing ma­chines and de­ci­sion prob­lems. In this con­text, the time com­plex­ity is as­so­ci­ated with the num­ber of steps a TM takes to halt and re­turn an out­put, while the space com­plex­ity cor­re­sponds to the length of the tape we would need for the TM to never fall off when mov­ing left or right.

One may worry that the com­plex­ity mea­sures are highly de­pen­dent on the choice of com­pu­ta­tional frame­work used. After all, if we al­low our TM to skip two spaces per step each time it moves it is go­ing to take po­ten­tially half the time to com­pute some­thing. How­ever, the asymp­totic be­hav­ior of com­plex­ity is sur­pris­ingly ro­bust, though there are some caveats.

The most in­ter­est­ing char­ac­ter­i­za­tion of com­plex­ity comes in the form of com­plex­ity classes, which break down the fam­ily of de­ci­sion prob­lems into sets of prob­lems which can be solved with par­tic­u­lar con­straints.

Per­haps the most im­por­tant com­plex­ity class is \(P\), the class of de­ci­sion prob­lems which can be effi­ciently com­puted noteFor ex­am­ple, check­ing whether a graph is con­nected or not. The sec­ond best known class is \(NP\), the class of prob­lems whose solu­tions can be eas­ily checked noteAn ex­am­ple is fac­tor­ing a num­ber: it is hard to fac­tor \(221\), but easy to mul­ti­ply \(13\) and \(17\) and check that \(13 \cdot 17 = 221\) . It is an open prob­lem whether those two classes are one and the same; that is, that ev­ery prob­lem whose solu­tions are easy to check is also easy to solve.

There are many more im­por­tant com­plex­ity classes, and it can be daunt­ing to con­tem­plate the sheer va­ri­ety with which com­plex­ity the­ory deals. Feel free to take a guided tour though the com­plex­ity zoo if you want an overview of some of the most rele­vant.

An im­por­tant con­cept is that of a re­duc­tion. Some com­plex­ity classes have prob­lems such that if you were able to solve them effi­ciently you could trans­late other prob­lems in the class to this one and solve them effi­ciently. Those are called com­plete prob­lems of a com­plex­ity class.


This page is meant to be a start­ing point to learn com­plex­ity the­ory from an en­try level. If there is any con­cept which feels mys­te­ri­ous to you, try ex­plor­ing the green­links in their or­der of ap­pear­ance. If you feel like the con­cepts pre­sented are too ba­sic, try a differ­ent lens.

Children:

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.