The human quest for efficiency is ancient and universal. Computational
Complexity Theory is the mathematical study of the efficiency
requirements of computational problems. In this note we attempt to
convey the deep implications and connections of the results and goals
of computational complexity, to the understanding of the most basic
and general questions in science and technology.
In particular, we will explain the P versus NP question of computer
science, and explain the consequences of its possible resolution, P =
NP or P 6= NP, to the power and security of computing, the human
q
...阅读全文