nLab
complexity theory

Contents

Contents

Idea

Computational complexity theory is the study of how much and how many resources are required to perform computations. Unlike other systems theories, computational complexity theory is purely mathematical and focuses on analysis of formal logic and abstract machines.

History

Historically, computational complexity theory arose from questions in computability theory and cryptography. In computability theory, we wanted to know what might be uncomputable relative to certain models of computation. In cryptography, we wanted to know which ciphers could be broken for a given amount of computational resources.

Current Directions

Today, the main focus of computational complexity theory is analysis of the complexity classes P and NP. Their relationship determines which of Impagliazzo's five worlds? is physical reality.

Additionally, descriptive complexity theory is an active research programme which characterizes complexity classes via formal logic rather than abstract machines.

References

Discussion of complexity classes via linear logic:

  • Pierre Boudes, Damiano Mazza, Lorenzo Tortora de Falco, An Abstract Approach to Stratification in Linear Logic (arXiv:1206.6504)

Last revised on September 28, 2021 at 13:23:37. See the history of this page for a list of all contributions to it.