确实，我们写在这里是一种“观察”，但却是一个认识：为什么复杂性理论与对NP的知识之间存在巨大差别？— 一个理论的专业性不应该是人们认知错误的来源。

我们探讨了库克的论文“理论证明过程中的复杂性”（The Complexity of Theorem-Proving Procedures），论文摘要中宣称：论文表明了，任何一个由不确定性图灵机在多项式时间内解决的判定问题，都可以“归约”为这样的问题：能否确定一个给定的命题逻辑式是否重言式。对此我们可以将论文的思路简要地理解为：NDTM可以转换为一种逻辑式并且可以是重言式。实际上，这就是论文中的定理1：如果一个符号串S被某种不确定性图灵机在多项式时间内接受，那末这个字符串S就是被P-归约到析取重言式。我们认为，这里的“P-归约”只不过是对NP的再定义。

我们在有关文章中指出，库克论文中的NDTM是一个成问题的再构造性定义（图灵机+神喻），但是库克运用这个NDTM定义作为文章证明的前提或论据（比如文章中定理1的论据就是“……那是因为每个集合或它的补集”是被某些不确定性图灵机在多项式时间内接受的“)。所以，在我们看来，所谓的库克“定理”不过是对NP的一个定义（由NDTM定义到重言式形式）而不是一个（运用“P-归约”）的定理。

由此可知，这篇文章中的这些术语“归约”、“再归约”、“P-归约”、或者“转换”，并不是“理论证明过程中的复杂性”，而只是对NP这个观念的再定义。或许我们可以这样说，所有这些一再定义的术语只不过表明难以完成对NP进行定义。当然，所谓的“NP-难”问题也不过只是对NP的再次重新定义。我们质疑NP的两个流行的定义，就是因为它们基于这样的错误的认知。

基于基本性的认识，我们认为NP的本质是图灵对希尔伯特第十问题的解决，而应当认为那是一种精确的数学推理。

*****

Cook’s theorem or Cook’s definition (NP)?

Indeed, what we write is a kind of « observation », but it is a kind of cognition: why is there a big gap between the complexity theory and the knowledge of NP? The professional nature of a theory should not become the source of people’s cognitive errors. 

We investigated Cook’s paper « The Complexity of Theorem-Proving Procedures », where its summary declaimed: « It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be ‘reduced’ to the problem of determining whether a given propositional formula is a tautology », which is in fact « Theorem 1 » in the paper： « If a set S of strings is accepted by some nondeterministic Turing machine with in polynomial time, then S is P-reducible to {DNF tautologies} ».

We have pointed out in our relevant articles，the NDTM in Cook’s paper is a problematic re-constructed definition (TM + oracle), but Cook used this NDTM as a premise or argument in his paper (for example, « …,This is because each set, or its complement, is accepted in polynomial time by some nondeterministic Turing machine »). In our opinion, this is only a definition of NP (from NDTM to tautology form), but not a theorem (by P-reducible).

Therefore, the terms in the paper such as « reduce », « re-reduce », « P-reduce » or « transition » do not concern “The Complexity of Theorem-Proving Procedures”, but only the re-definitions of the notion of “NP”. Maybe we can say that, the sense of all these re-re-definitions of terms just show the difficulty to compete a full definition of NP. Moreover, NP-hard is also a re-definition of NP. We question the two current definitions of NP, because they are all based on such cognitive errors. 

Based on the cognition about essentiality, we think the essence of NP is related to Turing’s resolution to Entscheidungsproblem (decision problem), which should be considered to accurate mathematical reasoning, …