Complexity Theory

Page #63 of Chapter: Crypto-for-the-rest-of-us

level indicator


Complexity theory is focused on the computational effort needed to solve problems where a growing number of items are involved.

In particular complexity theory asks: given a problem with some 100 items, how much more complicated would the problem be if we have 10 items more, (110 all together)?

It is related to cryptography because it tells us how much more complicated for the adversary will be a problem where a key of say 100 digits is replaced with a key of 110 digits.

We are looking for problems where the computational burden increases dramatically with a modest increase in key size (items count).

We are concerned about problems that appear complicated but nonetheless hide a mathematical shortcut that we missed, but our adversary discovered.

Illustration: to compute the distance covered by a fly flying from nose to nose of two people approaching each other at known speeds may involve adding the shrinking distances of all the flying segments (tedious), but may be shortcut by multiplying the fly's speed times the time lapsed for the two people to meet.

The coveted goal of complexity theory is to prove that what appears complex to us, does not hide a mathematical shortcut that we have overlooked. Such proof (known as P=NP) remains elusive.

* Version CE-H6703 (SERVER) Crypto Academy