Interpretation of Cook”s theorem-What is NP?
We investigate the notion ofnondeterminism that has been neglected in the theory of N P-completeness.From the cognitive perspective, we trace the origin of nondeterminism, and from there we examine how nondeterminism was raised and then lost, and study how it can be recovered.We interpret Cook”s theorem and the two definitions of NP.We reference a famous paradox of Chinese philosophy, called ”white horse not horse”, to further analyze the cognitive biases in understanding NP.Such an investigation allows us to review the P versus NP problem.We hope that this work can evoke reflections from different angles about some fundamental problems in cognitive science, and contribute to the progress of the theory of NP-completeness.We also hope that this work can evoke reflections about the complementarity between Chinese and Western cultures.
cognitive theory of NP-completeness nondeterminism decision problem P versus NP Cook”s theorem ”white horse not horse”
Yu LI
Institut of computational theory and application,Huazhong University of Science and Technology,Wuhan,China
国内会议
西安
英文
474-481
2013-10-18（万方平台首次上网日期，不代表论文的发表时间）