$P,NP$ and mathematics – a computational complexity perspective

Abstract

The P versus NP question distinguished itself as the central question of theoretical computer science nearly four decades ago. The quest to resolve it, and more generally, to understand the power and limits of efficient computation, has led to the development of computational complexity theory. While this mathematical discipline in general, and the P vs. NP problem in particular, have gained prominence within the mathematics community in the past decade, it is still largely viewed as a problem of computer science.

In this paper I shall try to explain why this problem, and others in computational complexity, are not only mathematical problems but also problems about mathematics, faced by the working mathematician. I shall describe the underlying concepts and problems, the attempts to understand and solve them, and some of the research directions this led us to. I shall explain some of the important results, as well as the major goals and conjectures which still elude us. All this will hopefully give a taste of the motivations, richness and interconnectedness of our field. I shall conclude with a few non computational problems, which capture P vs. NP and related computational complexity problems, hopefully inviting more mathematicians to attack them as well.

I believe it important to give many examples, and to underlie the intuition (and sometimes, philosophy) behind definitions and results. This may slow the pace of this article for some, in the hope to make it clearer to others.