关于P/NP问题的定义理解

姜咏江

   研究P/NP问题，最关键要正确理解其定义。在维基百科网站上，P/NP问题是这样定义的：

The class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.

   而在百度上见到的中文定义是：

复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。

      P/NP问题的要点概念包括：确定型图灵机、多项式时间、给定正确信息、非确定型图灵机、解决的问题等。这些概念中确定型图灵机和非确定型图灵机都有数学方法给出的定义，其余的几个概念都似乎不大清楚。其中最要命的是所谓多项式时间，其不明确性简直是数学史上罕见。

   不确定的问题就需要讨论，或许P/NP问题之难就出在那些模糊的概念上。首先我们要弄懂问题的定义。对于问题我们似乎很熟悉，但要将其放到定义的层面上，确实不好准确给出。

   从问题组成的角度来看，一个问题要有条件及适合条件的结果这两部分组成。由条件怎样就得出了结果？这中间要经过推理、推导、计算、替换等一系列环节。这些中间环节今后我们一律用计算替代。我们可以如下给问题下定义。

定义：从条件出发，经过计算，最终得出结果的过程称为问题。

   可以知道，条件、计算和结果是问题组成的三要素。从条件出发，经过计算，最终得到确定结果的情况，我们称问题有解，得不出确定结果的情况，称为无解。NP类问题定义中说的“positive solutions”就是有解吧？

例如，有条件x²-x-6=0，经过计算.得到x=3或x= -2这两个确定的结果。这说明这个求方程根的问题有解。

   实际问题当中的条件常常很复杂，因而计算的过程也不会象上面这个例子那样简单，如果用计算机来计算，一般需要编写复杂的程序，通过程序在计算机上执行，最后才能得到有解或者无解。

   回到NP的中文定义“类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成”来看，似乎对验证的理解有误。

   所谓验证（或者叫判定）总是从某些不完备的信息（不能用单独的部分条件或只是指猜测结果）出发，去寻找完备信息的过程。因而所谓“给定正确信息”大概是我们猜测，这是翻译者对文中内容不甚理解加上去的条件吧?如果一个需要判定的问题，已经给定了正确信息，那么只要按照正确信息的条件计算下去，那就可以知道问题是否可解，还提什么验证判定的意思呢？

   这是我们的翻译问题还是英文表述的原意就是如此？请精通英文的专家能够解释一下。

我想真正能够准确地表达NP问题，是否应该这样定义：类NP由所有可以在多项式时间内验证其给定信息正确的肯定解所确定的问题组成。

    有关的其它概念，我们暂不在此讨论。

补充：有的叙述将验证最终回答是“yes/no"做为NP问题的表述，那就会造成回答yes或no都属于NP的问题。虽然判定属于NP的问题是需要回答“yes/no"，但以”no“回答的那些问题显然不应该属于NP。

2015-6-17