在现有的NP完备理论（Theory of NP-Completeness）中，一个典型的观念就是：“NP是可计算，但是难计算的”，如此，就有如下的问题分类：　 　　　　　　　　　　　　

　　　　　　　　　　　　　　　                                       问题

　　　　　　　　　　　　　　　　　　　┌───────┴───────┐

　　　　                         　　　　　  可计算（可判定）问题　　　　　　　不可判定问题（判定问题）

　　　　　　　　　　　　　　　┌───┴───┐　　　　　　　

　　　　                                易计算（P）           难计算（NP）　　　　　　

因为流行的NP定义（Nondeterministic Polynomial time）基于NDTM（NonDeterministic Turing Machine），而NDTM的本质是“可判定，可计算”，至此NP就与“判定问题”脱离了关系，而相应的NP完备理论也与可计算性理论无关了。

“NP是可计算，但是难计算”的理由是，“NP存在着指数时间复杂度（精确求解）的算法，但目前还没找到多项式时间（精确求解）的算法”。我们认为，这样的观念存在着认知错误，其根源在于人们未深究“可计算性”的本质。

首先，“算法”是计算“实例”的，若一个算法具有“多项式时间复杂度”，表明机器的计算能力能胜任问题实例的规模增长，也就是图灵机的“可计算性”的意义。在这种情况下，可以推导出：对应的“问题”是“可计算的”，这实际上就是P的定义。

但是若算法具有“指数时间复杂度”，则说明机器的计算能力不能胜任问题实例规模的增长。比如：基于“穷举法”求解“SAT问题”的DPLL算法，由于其搜索空间是指数型，故相应的算法复杂度是“指数型”：O(2^n)，n是“SAT问题”实例的规模。虽然DPLL能计算一些SAT问题实例，却不能一般性地推导出：DPLL能计算任何SAT问题实例，即不能说“SAT问题是可计算的”，所以：

1，当输入规模是“常量”时，针对“SAT问题实例”，“难”但“可计算”；

2，当输入规模是“变量”时，针对“SAT问题”，就“难”到“不可计算”了。

这就是我们反复分析的“实例与问题、常量与变量”所涉及到的“个别与一般”的二个不同层次，这类似于“人”的二个不同层次，比如说：“保持公共场所卫生，人人有责”，就不能说成“人类有责” 。正是在此意义上，我们认为：NP不是难计算，而是“难”到不可计算！

由于NP毕竟还是需要用计算机来“计算”的，为避免悖论的“不可说”，我们把NP定义为“不确定性问题（Nondeterministic Problem）”，而不称“不可计算问题”；把求解NP的算法定义为“不确定性算法（Nondeterministic Algorithm，NP－Algorithm）”，是有新的问题分类：　　　　　　　　　　　　　

　　　　　　　　　　　　　　　                                       问题

　　　　　　　　　　　　　　　　　　　┌───────┴───────┐

　　　　                         　　　　　可计算问题（P）　　         不确定性问题（NP，判定问题）

如此，相应的理论就是与“可计算性理论”相对的“不确定性理论”（NP理论）了。

由此可见，我们的NP（Nondeterministic Problem）定义的基础是可计算性理论、图灵机和判定问题（Entscheidungsproblem），与流行的NP（Nondeterministic Polynomial time）定义有本质的区别，旨在还原NP消失了的“不确定性”。