Book contents
- Frontmatter
- Contents
- The Independent University of Moscow and Student Sessions at the IUM
- Mysterious mathematical trinities
- The principle of topological economy in algebraic geometry
- Rational curves, elliptic curves, and the Painlevé equation
- The orbit method and finite groups
- On the development of the theory of dynamical systems during the past quarter century
- Foundations of computational complexity theory
- The Schrödinger equation and symplectic geometry
- Rings and algebraic varieties
- Billiard table as a playground for a mathematician
- The Fibonacci numbers and simplicity of 2127 – 1
- On problems of computational complexity
- Values of the ζ-function
- Combinatorics of trees
- What is an operad?
- The orbit method beyond Lie groups. Infinite-dimensional groups
- The orbit method beyond Lie groups. Quantum groups
- Conformal mappings and the Whitham equations
- Projective differential geometry: old and new
- Haken's method of normal surfaces and its applications to classification problem for 3-dimensional manifolds – the life story of one theorem
Foundations of computational complexity theory
Published online by Cambridge University Press: 18 December 2009
- Frontmatter
- Contents
- The Independent University of Moscow and Student Sessions at the IUM
- Mysterious mathematical trinities
- The principle of topological economy in algebraic geometry
- Rational curves, elliptic curves, and the Painlevé equation
- The orbit method and finite groups
- On the development of the theory of dynamical systems during the past quarter century
- Foundations of computational complexity theory
- The Schrödinger equation and symplectic geometry
- Rings and algebraic varieties
- Billiard table as a playground for a mathematician
- The Fibonacci numbers and simplicity of 2127 – 1
- On problems of computational complexity
- Values of the ζ-function
- Combinatorics of trees
- What is an operad?
- The orbit method beyond Lie groups. Infinite-dimensional groups
- The orbit method beyond Lie groups. Quantum groups
- Conformal mappings and the Whitham equations
- Projective differential geometry: old and new
- Haken's method of normal surfaces and its applications to classification problem for 3-dimensional manifolds – the life story of one theorem
Summary
This lecture is intended for those who are not acquainted with the theory of computational complexity. For this reason, I shall talk only about the foundations of this theory and its very first results. I shall try to deliver the main ideas which guide the researchers in this field of science.
The setting of my narrative are stories about one personage called M (for “mathematician”). I shall start with the following story.
Prehistory
Once upon a time, M sat at home trying to prove some (maybe important, or maybe not) theorem T. He tried to prove this theorem for a week, two weeks, a month, …, but with no result. In the end, he gave up and asked quite the natural question:
Why, can this theorem be proved at all?
The question was addressed to nobody; most likely, it would fly away if another personage, L (for “logician”), would not pass by.
L heard the question, came into the room, and explained that such questions started to interest mathematicians some time in the beginning of the twentieth century. In a general setting, this question is contained in the famous Hilbert's Program devoted to the notion of mathematical proof.
This program, in particular, included the following three items.
Formalization of the notion of proof. Before asking whether or not an assertion can be proved, we must give a rigorous mathematical definition of provability.
[…]
- Type
- Chapter
- Information
- Surveys in Modern Mathematics , pp. 186 - 202Publisher: Cambridge University PressPrint publication year: 2005
- 1
- Cited by