silversilkroad

By Avi Wigderson





Abstract
The
P
versus
NP
question distinguished itself as the central ques-tion of theoretical computer science nearly four decades ago. The quest
to resolve it, and more generally, to understand the power and limits ofefficient computation, has led to the development of computational com-plexity theory. While this mathematical discipline in general, and the
P
vs.
NP
problem in particular, have gained prominence within the mathe-matics community in the past decade, it is still largely viewed as a problemof computer science.
In this paper I shall try to explain why this problem, and others incomputational complexity, are not only mathematical problems but also
problemsabout mathematics, faced by the working mathematician. I shalldescribe the underlying concepts and problems, the attempts to under-
stand and solve them, and some of the research directions this led usto. I shall explain some of the important results…..
ReadMore...
https://silversilkroad.files.wordpre...014/11/w06.pdf