博文
纠正对NP 问题的错误理解 --一篇文章的读后感
|||
纠正对NP 问题的错误理解
--一篇文章的读后感
郝克刚 2011-12-24
最近读到一篇文章，在某专业杂志专家论坛栏目中发表。其中涉及著名的NP ≠ P问题，我发现他对NP 问题的理解有误，这也是有些非专业人士常有的错误理解，特在此做些解释。我先把该文章中所有涉及NP 问题的段落列举如下:
【 摘 要：……计算复杂性（其中揭示了一个基本原理——NP ＝ P 当且仅当 N 可有可无）……
0 引 言………笔者视其为在可计算数范围内如何降低计算复杂度的问题 [3]，既涉及多项式时间内的计算问题，即P问题[4]，又涉及非多项式时间内的计算问题，即 NP 问题 [5]，还涉及 P ＝ NP 或 NP=P 的 NP完全问题 [6]——笔者认为如何判定 NP ≠ P 或 NP ＝ P 是整个问题的一个难点或焦点，涉及图灵测试 [7]或怎样才可顺利通过图灵测试而具有人工智能的问题。……至超级计算的虚拟计算模型。其意义还在于孪生图灵机以自然语言的计算复杂性问题为例可揭示一个基本原理，即：NP=P 当且仅当 N 可有可无。下面分别从孪生图灵机及其“天平”原理，受限模式与派生模式及其优化算法，NP=P 成立的条件（即“N 可有可无”）或前提（即“可计算、能判断且易计算”与否）来论述。
1 孪生图灵机及其“天平”原理……由此可见，图 1、图 2 和图 3 所示内容，虽然在笔者看来均是“显而易见”的 P 问题，然而，在读者看来却完全可能是“非显而易见”的 NP 问题。这是为什么呢？因为，只有充分公开“转化条件”或“转变步骤”，才能把原创者清楚的“非显而易见”的情形（NP 问题）转化为重用者也清楚的“显而易见”的情形（P 问题）。否则只能盲搜。……
3 NP=P 成立的条件……图1至图13所示内容，既是“显而易见”的P问题，也是“非显而易见”的 NP 问题。其区别和联系仅在于是否把握 NP=P 成立的条件。
4 结论 ……。理解它的各环节需要区分显而易见（P 问题可视为其一类特例）和非显而易见（NP 问题也可视为其另一类特例）两类情形，进而掌握由P到NP的理解与由NP到P的表达两个转化过程成立的条件（即N可有可无）。这是理解继承与创新、学习与创造、“显而易见”与“非显而易见”以及广义的 P 问题与 NP 问题及其相互转化的关键。本文明确解答这样一个问题，即：如何把“非显而易见”转化为“显而易见”？关键在于证明两点：其一就是证明 P ≠ NP（即：区分两者）；其二则是证明 P ＝ NP 当且仅当 N 可有可无（即：找出两者相互转化的条件）。……】
评论
1, NP问题不是“非多项式时间内的计算问题”
严格地讲，P代表在多项式时间界限下，确定的图灵机器所接受的语言类，NP代表在多项式时间界限下，非确定的图灵机器所接受的语言类。
这里的N指的是非确定（nondeterministic）的图灵机器，而不是“非多项式时间”。有些人以为既然P代表多项式，就错误地望文生义以为NP就代表非多项式，这其实是错误的理解。
所谓确定的机器，是指在机器执行中至多只有一个规则适用，从而机器每步的执行动作是确定的。然而非确定的机器在执行中可能有多个规则适用，从而机器每步的执行动作有多种可能，是不确定的。
2，P=NP还是P≠ NP？不叫NP完全问题。
P=NP还是P≠ NP？即“在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能？”
这个问题的提法相当清晰，但是要解答这个问题却不容易。当代很多有名的计算机科学家都研究了这个问题，这是至今尚未解决的世纪七大难题之一。
上世纪70年代此问题有重大突破。S. A. Cook (1971)和R. M. Katp (1972)首先提出了P归结和NP完全的概念：。
如果一个语言L0满足条件L0 ∈ NP而且对于NP中的任何语言L，L都可以P归结为语言L0 。则称L0是NP完全的，而且证明了命题逻辑公式的可满足性问题是NP完全的。
这就把P=NP问题归结为一个具体的语言（问题）是否属于P的问题。如果命题逻辑公式的可满足性问题属于P则P=NP，否则P≠ NP。后来证明了一大批问题都是 NP 完全问题。
可参考我2006年给学生们做的一个学术报告。
讲稿下载：2006-11-lec-1.pps
3，P和NP有明确的固有的定义，不能随意地把P说成是代表“显而易见”，NP是代表“非显而易见”。还说这是“理解继承与创新、学习与创造”” 广义的 P 问题与 NP 问题及其相互转化的关键”。走得太远了，同P和NP问题的原有的定义已经不沾边了。
https://blog.sciencenet.cn/blog-506146-521648.html
上一篇：乔布斯(Steve Jobs)的两段精彩讲话
下一篇：纠正对NP 问题的错误理解（2）-- 对网友评论的回复
