Extending Wednesdays

Computational Complexity

Today’s Extending Wednesdays topic comes from the Computer Science section of Ideas Roadshow’s Extended Essay Guide, where pioneering “quantum cryptographer” Artur Ekert, Professor of Quantum Physics at University of Oxford & National University of Singapore, describes the notion of computational complexity, a way of objectively distinguishing between “easy” and “hard” mathematical problems.

Well, you might be forgiven for thinking, that is all very interesting in an abstract sort of way, but does it have any real practical value?  The answer turns out to be a resounding “yes” – indeed, it is, quite frankly, hard to think of something that has greater practical value. The entire notion of complexity classes was originally formulated to solve the “key distribution problem” of cryptography and led directly to the development of security protocols that are used to encrypt every current financial transaction on the internet.  

And, as is usually the case for science, developing the idea of computational complexity also helped lead to a whole host of additional intriguing concepts, from quantum algorithms to the very nature of “information”.  

This topic bridges computer science, mathematics and physics.  Possible areas of investigation for an extended essay include an examination of the history of computational complexity, cryptography’s key distribution problem, current public key cryptographic protocols, classical vs. quantum algorithms and quantum cryptography. 

Related Ideas Roadshow content includes the two hour-long videos Cryptoreality Part I and Cryptoreality Part II, as well as the clips The Physics of Information and Applied Philosophy