The history and status of the P versus NP question
The history and status of the P versus NP question
复制标题
P 与 NP 问题的历史和现状
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
M. Sipser
中科院分区：
文献类型：
--
作者：
M. Sipser
The P versus NP question grew out of developments in mathematical logic and electronic technology during the middle part of the twentieth century. It is now considered to be one of the most important problems in contemporary mathematics and theoretical computer science. The literature on this subject is diverse but not huge — it is possible for the student to acquaint himself with all of the important relevant work in a semester or two. In writing thw article, I have attempted to organize and describe this Literature, including an occssiom-d opinion about the most fruitful directions, but no technical details. In the first half of this century, work on the power of formal systems led to the formalization of the notion of algorithm and the realization that certain problems are algorithmically unsolvable. At around this time, forerunners of the programmable computing machine were beginning to appear. As mathematicians contemplated the practical capabilities and limitations of such devices, computational complexity theory emerged from the the ory of algorithmic unsolvability. Early on, a particular type of computational task became evident, where one is seeking an object which lies
