我们的NP理论工作首重解读NP的二个流行定义及二个定义的关系，这篇英语文章是此工作的总结和深化。 文章追本溯源分析用于定义NP的NDTM（不确定性图灵机），揭示NDTM指称二个完全不同的概念：一个是Oracle（神喻机），另一个是Turing Machine（图灵机）。由于同一术语NDTM指称两个内涵完全不同的概念，故发生了“概念偷换”的逻辑错误，导致“可验证”成为现在NP的标准定义，自此NP的本质“不确定性”消失了，遂有“P versus NP”的千禧年难题。 由于NP的原始定义与Oracle有关，而Oracle又来自图灵关于“可计算性”的工作，故追本溯源到图灵的工作，应该是澄清NP定义的正途，也即我们的NP理论基于可计算性的深刻背景。 ＊＊＊＊＊＊ In this paper, we interpret NDTM (NonDeterministicTuringMachine) used to define NP by tracing to the source of NP . Originally NP was defined as the class of problems solvable in polynomial time by a NDTM in Cook’s theorem, where the NDTM was represented as Query Machine of essence Oracle . Later a model consisting of a guessing module and a checking module was proposed to replace the NDTM . This model of essence TM has a fundamental difference from the NDTM of essence Oracle , but people still use the term NDTM to designate this model, which leads to the disguised displacement of NDTM and produces out the verifier-based definition of NP as the class of problems verifiable in polynomialtime by a TM (Turing Machine). This verifier-based one has been then accepted as the standard definition of NP where comes from the famous equivalence ofthe two definitions of NP . Since then the notion of nondeterminism is lost from NP , which causes ambiguities in understanding NP and then great difficulties in solving the P versus NP problem. Since NP is originally related with Oracle that comes from Turing’s work about Computability , it seems quite necessary to trace back to Turing’s work and clarify further the issue about NP . interpretationNDTMCiE.pdf
标签: 英语文章
