目前为止，我们直接针对NP的流行定义：“NP是多项式时间可验证的问题”，解读其认知错误。我们指出，此认知错误来自于混淆了“nondeterministic Turing machine”二个不同的内涵：NTM（非图灵机）和NDTM（不确定性图灵机），从而得出NP二个定义等价，致NP的“不确定性”消失。

另外，还存在着一个更加令人困惑的流行观点：NP是可计算的，理由是，NP存在指数时间复杂度算法。

我们在博文“什么是‘判定问题’？（1）－可计算性理论与计算复杂性理论”（http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=895834）中，简单回顾了算法理论的历史，指出：此观念直接导致计算复杂性理论（Computational complexity theory）与可计算性理论（Computability theory）相分离的现状，使作为计算复杂性理论基础的NP完备理论（NP－completeness theory），成了无源之水，无本之木！

这里，我们希望解读“NP存在指数时间算法”的意义，由此出发逐步解读“NP是可计算的”，为此，我们借用具有代表性的“SAT问题”来帮助解读。

SAT问题，是“布尔逻辑可满足性问题（boolean SATisfiability problem）”的简称，指给定一个合取范式的布尔公式，判断其是否可满足。SAT问题是逻辑学的一个基本问题，也是算法理论的核心问题，因为任何一个欲通过算法求解的问题（P和NP）都可表达为SAT问题：2-SAT是P问题（确定性问题）的代表；3-SAT是NP问题（不确定性问题）的代表。

然而SAT问题与P和NP的关系，学术界一般用所谓的“归约（reduction）”来阐释，即将SAT问题与P和NP相互表达，但是于认知问题的角度，此“归约”只是停留在问题的表面，并未深入问题的本质，就好比问“老王在哪里”，却被告知“老王在老张的隔壁”，而老张比老王更难找，因为还不认识老张。

所以，我们希望通过对SAT问题本身作些必要的解读，来帮助认知P和NP。我们先阐释“问题”、“实例”与“解”的层次表达，并用哈密顿路径问题表达为SAT问题的案例说明之：

一，“问题”、“实例”与“解”的层次表达

“问题（problem）”、“实例（instance）”和“解（solution）”是算法理论中最基本的概念，只是对这些概念的解释一般未作层次的分辨（见附录）。

从日常语言的角度，“问题”指：对事物，问是否具有某种“性质”。

从算法语言的角度，“问题”指：对任何一个问题实例，问是否存在具有某种性质的“解”；“性质”指约束条件，“解”指满足约束条件的结构。“问题”与“实例”相对而言，“问题”是“实例”的抽象形式。

从逻辑语言的角度，一个约束条件可表达为“子句”，子句Ci（1≤i≤m）是文字的析取式：l1∨l2∨…∨lk，文字li（1≤i≤k）为某一布尔变量或该布尔变量的非；若干约束条件可表达为诸子句的合取式F：C1∧C2∧…∧Cm，即合取范式。合取范式F表达“解”的结构，SAT问题（也称合取范式的可满足问题）指：问是否存在一组布尔变量的赋值（解），使得整个合取范式F取值为真？

于是，一个欲通过算法求解的问题表达成了SAT问题，正是在此意义上，SAT问题在算法理论和问题求解中都占有重要地位。

二，案例：哈密顿路径问题表达为SAT问题

我们以哈密顿路径问题为例（见博文“参详P与NP的二个实例“－http://blog.sciencenet.cn/blog-2322490-878672.html）：

问题：任给一个有向图G及二个结点s和t，问在G中是否存在一条从s到t且遍历G的所有结点的路径（哈密顿路径）？

实例：如图1，来自Sipser的书。

通过表达哈密顿路径所须满足的约束条件，把哈密顿路径问题表达为SAT问题，其步骤如下（并用实例图1说明之）：

1，定义布尔变量

xij = 1，哈密顿路径中第i位子是结点j

xij = 0，哈密顿路径中第i位子不是结点j

哈密顿路径中有n个位置，故每个结点有n个布尔变量，共有n＊n布尔变量：

2，定义字句

（1）每个结点j只能在哈密顿路径中出现一次

x1j ∨x2j ∨···∨xnj

¬xij ∨ ¬xkj ， i ̸= k

比如，结点1只能在哈密顿路径中出现一次：

x11 v x21 v x31 v x41 v x51 v x61 v x71v x81

¬xi1 v ¬xk1 ， i ̸= k

（2）哈密顿路径中的每个位置i只能有一个结点

xi1 ∨xi2 ∨···∨xin

¬xij ∨ ¬xik， j ̸= k

比如，位置1只能有一个结点：

x11 v x12 v x13 v x14 v x15 v x16 v x17 v x18

¬x1j v ¬x1k ， j ̸= k

（3）不是相邻的二个结点不能在哈密顿路径中相邻出现

¬xki ∨¬x(k+1)j， (i,j） ̸∈G，k=1,2,...,n−1

比如，结点1，4不能在哈密顿路径中出现：

¬xk1 ∨¬x(k+1)4， (1,4） ̸∈G，k=1,2,...,n−1

3，定义合取范式公式

F由上述子句的合取式构成。

4，定义SAT问题

任给一个合取范式F，问是否存在一组布尔变量的赋值，使得F取值为真？

于此实例，F是可满足的，比如，x11=true, x23=true, x35=true, x44=true，x52=true，x66=true，x77=true，x88=true，令其余布尔变量为false，此组变量赋值使F＝true，代表哈密顿路径：1－3－5－4－2－6－7－8。

＊＊＊＊＊＊

附录：

1，在Garey，Johnson的书（Computers and Intractability - A guide to the Theory of NP-Completeness）中第一章的第二节（p.4）：

1.2 Problems, Algorithms, and Complexity

Let us begin with the notion of a problem. For our purposes, a problem will be a general question to be answered, usually possessing several parameters, or free variables, whose values are left unspecified. A problem is described by giving : (1) a general description of all its parameters, and (2) a statement of what properties the answer, or solution, is required to satisfy. An instance of a problem is obtained by specifying particular values for all the problem parameters.

As an example, consider the classical "traveling salesman problem". The parameters of this problem consists of a finite set C = {c1, c2, …, cm} of "cities" and, for each pair of cities ci,cj in C, the "distance" d(ci,cj) between them. A solution is a tour of minimum length.

One instance of the traveling salesman problem, illustrated in Figure 1.1, is given by C={c1,c2,c3,c4}, d(c1,c2)=10, d(c1,c3)=5, d(c1,c4)=9, d(c2,c3)=6, d(c2,c4)=9, and d(c3,c4)=3. The ordering <c1,c2,c4,c3> is a solution for this instance, as the corresponding tour has the minimum possible tour length of 27.

2，维基网（https://en.wikipedia.org/wiki/Computational_complexity_theory）：

Problem instances

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g. 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case "no"). Stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input.

To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometers passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.