姜咏江

《算法导论》一书中文译本，对NP完全性问题有如下的解释，研究中发现似乎不够准确，有必要探讨一下。

Np completeness applies directly not to optimization problems, however, but to decision

problems, in which the answer is simply “yes” or “no” (or, more formally, “1” or “0”).

书中翻译：NP完全性不适于直接应用于最优化问题，但适合于用于判定问题（decision problem），因为这种问题的的答案是简单的“是”或“否”（或者，更为形式化地，答案是“1”或“0”）。

对于decision  problem的中文翻译我一向很纠结，是翻译成“判定问题”、“决定问题”还是“确定问题”？到底哪种翻译能够确切地表达NP问题的确切意思？

“判定”和“决定”这两个词多少都带有“主观”的成分，而“确定”不指出主体，在中文中具有客观性。

在维基百科中对decision  problem是这样解释的：

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable.

这一段如果不研究，似乎可以译为“判定（决定）问题”。再看看最后一句话：一些数学当中最重要的问题是不可判定（决定）的。

什么样的数学问题是不可判定的？那就是你无论给出怎样的输入，都不可能得到“是”或“否”的回答！由此来看，decision  problem应该译成“确定问题”为好。

验证问题，是给出一些问题的输入，通过问题本身的特定条件，最终得出“是”与“不是”问题答案的过程。一次验证不能确定问题是否有解，但验证输入满足条件，证明是问题答案的时侯，也可以得到“是”的回答，否则会得到“否”的回答。而decision  problem的特征是“否”的结论产生，就不可能再出现“是”的回答了。

decision  problem是对问题的全体输入情况回答“是”与“否”，而验证回答的是具体输入回答“是”与“否”。前者具有确定性，后者具有随机性。因而将P/NP问题定义中的decision  problem译为确定问题应该是最准确。

2016-11-20