Computational Complexity Theory focuses on understanding why certain problems are difficult to solve efficiently with respect to computational resources such as time and space. This is explored through the interplay between models of computation and concrete computational problems. For models of computation that are sufficiently restricted, it is possible to prove that problems of interest cannot be solved efficiently. Such results typically have direct implications for other areas of computer science, such as data structures and cryptography. In other cases, such results can only currently be achieved under plausible assumptions.  

The social impact of Complexity Theory stems from its applicability to various areas of computer science and beyond. Computational hardness as a phenomenon has far-reaching consequences in practical settings as well as in other scientific disciplines both within and outside of computer science. In everyday life, it can be harnessed, for example, to enable secure transactions on the Internet through public key cryptography. On the other hand, it poses a computational challenge, such as in mathematical optimization. Here Complexity Theory helps practitioners to direct their intellectual effort towards the most appropriate ways to approach the solution of concrete computational problems.