P、NP、NPC、NPH

NPC

问:什么是NP完全性问题?

答: NP完全性问题属于＂计算复杂性＂研究的课题。 所谓计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准有两个:

一是计算所需步数或者指令数（时间复杂度）；

二是计算所需的存储单元数（空间复杂度）。

它不是对一个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类，即复杂性类。

NP中的某些问题的复杂性与整个类的复杂性相关联，而这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。这些问题称为NP完全的。

问题:什么 是NP完全问题?

答:NP完全问题（NP-C问题），是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP＝P?，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

问题:所有的NP问题都是多项式时间可以判定的吗?

答:NP类中有某些问题的复杂性与整个类的复杂性相关联。如果能找到这些问题中的任何一个的多项式时间判定算法，那么，所有的NP问题都是多项式时间可以判定的。

什么是NP完全问题?

要解决P ＝ NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行商问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内，则P ＝ NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P ＝ NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

问:什么是NPC问题?

答: 在理论信息学中的计算复杂度理论领域里NPC指NP完全问题（Non-deterministic Polynomial complete problem）。

简单的说，如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NPC问题。

如果所有NP问题都能在多项式时间内转化为某NP问题，则称该NP问题为NPC问题。

请简述怎么证明一个问题A是不是npc问题?

答:首先证明A是一个np问题；找到一个np完全问题B，证明B归属于A。

问题:经典的NPC问题有哪些?

答:汉密尔顿回路/路径问题，货郎担问题（旅行推销员问题），集团问题，最小边覆盖问题（注意和路径覆盖的区别），背包问题等都是NPC问题

问:什么是旅行商问题?

答:旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。

问题:NP完全问题的近似解法?

答:1．使用动态规划、回溯法或分支限界法求解；

2、使用遗传算法、模拟退火。

问:当必须求解NP完全问题时，应该怎么处理?

答:

1）只运行小的问题实例

不是所有问题都接受该方法。如TSP问题。

2）解决这个问题的一个不太困难的实例

问题:求解NP完全问题有哪几种处理方法?

答:①只运行小的问题实例:但不是所有问题都接受该方法。如TSP问题。

②解决这个问题的一个不太困难的实例:如，顶点覆盖问题。若假设图为二部图（图分为两部分，每个子集内部的两个顶点之间无边），则可在多项式时间内求解。

P

问:P类问题是什么?

答:P表示确定的TM在多项式时间（步数）内可判定的语言类。这些语言对应的问题成为是P类问题，这种语言称为多项式可判定的。

问题:有哪些问题是P类问题?

答:P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。

如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。

P类问题就是所有复杂度为多项式时间的问题的集合。

我们通常在编程中求解的问题大多都是P类问题．比如说排序，找最短路径等．

NP

问题:“NP表示不确定的TM在多项式时间（步数）内可判定的语言类”的另一种定义?

回答:NP表示确定的TM在多项式时间（步数）内可验证的语言类。

问:什么是NP问题?

答:NP表示不确定的TM在多项式时间（步数）内可判定的语言类。这些语言对应的问题称为是NP类问题（class of NP） ，也称这些问题是NP复杂的，或者NP困难的。这种语言称为非确定性多项式可判定的。

问题:什么是NP类问题?

回答:在多项式时间内由非确定性算法判定式求解的一类问题；也可以理解为在多项式时间内由确定性算法验证或者检验的一类问题。

问:请简述NP问题的两种定义

答:

1、在多项式时间内用不确定算法可以判定或求解的问题；

2、在多项式时间内用确定算法可以检验或验证的问题。

求解NP类问题的常见方法有什么?

对于那些棘手的NP问题，我们也并非束手无策，有一些方法可供我们去探究NP问题。

1近似算法

2并行计算

3智能算法

P NP

计算复杂性是什么?可以分为哪几类?

1）计算复杂性:算法所需计算时间的多少；

通俗说来，就是用计算机求解问题的难易程度。

其度量标准:

一是计算所需的步数或指令条数（这叫时间复杂度），

二是计算所需的存储单元数量（这叫空间复杂度）。

2）可分为两类:

a）P类:确定的算法，以多项式时间求解。确定型单带图灵机在多项式时间内可判定的语言类。

b）NP类:不确定算法，以多项式时间求解。具有多项式时间验证机的语言类。

问题:计算复杂性中包含了两类算法，请简要说明。

答案:P类问题:P类算法是确定的算法，可以用多项式时间求解（也就是可处理的）；NP类算法是不确定算法，以多项式时间求算不可求解。

(一)定义

P类问题和NP类问题的定义分别是什么?

（1）如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

（2）NP问题是指可以在多项式的时间里验证一个解的问题。

NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

问:什么是P类问题?什么是NP问题?

答:P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。

NP问题是可以在多项式时间内验证一个解是否正确的问题。所有的P类问题都属于NP问题。

问题:什么是P?什么是NP?

答:类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；

类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成。

其中多项式时间指的是一个问题的计算时间m（n）不大于问题大小n的多项式倍数。

问题:给P问题和NP问题下定义。

回答:．P问题是可以在多项式时间内被确定机（通常意义的计算机）解决的问题。NP（Non-Deterministic Polynomial， 非确定多项式）问题，是指可以在多项式时间内被非确定机（他可以猜，他总是能猜到最能满足你需要的那种选择，如果你让他解决n皇后问题，他只要猜n次就能完成----每次都是那么幸运）解决的问题。

(二)理解

问:怎样理解P问题和NP问题?

答:P问题的定义是确定型图灵机在多项式步数给出问题的解，

而NP是非确定型图灵机在多项式时间内给出问题的解，

两个问题的唯一区别就是是否存在不确定性行为．

怎么理解p和np问题?

P问题的定义是确定型图灵机在多项式步数给出问题的解，而NP是非确定型图灵机在多项式时间内给出问题的解，两个问题的唯一区别就是是否存在不确定性行为．

P和NP，区别就在于确定型图灵机和非确定型图灵机了．为啥定义图灵机呢，而不说自动机，下推机之类的，主要由于它可以处理任意可计算的问题．而其他东西都有一定局限性．NP和P就是一个确定一个非确定，并且P问题属于NP问题，由于确定型图灵机属于不确定型图灵机（不确定型就是操作的行为不确定，可以用不确定型自动机的概念去理解，但是不确定型图灵机不等于确定性图灵机，它们是包含关系）

(三)关系 包含 属于

问题:P类问题和NP类问题的关系?

答:P类问题包含于NP类问题。答:P类问题是NP类问题的一种特例。

如何解释P⊆NP?

答案:p是可以在多项式时间里求解的，也就是可以在多项式时间里求证的，所以p一定包含于np。

问题:P包含于NP中，对吗?为什么?

答案:对的，因为如果一个问题可以在多项式时间内被确定机解决，则它属于P类问题；

如果它可以在多项式时间内被非确定机解决，则它属于NP类问题。

显然确定机是非确定机的特例，所以P包含于NP。

问题:请说明为什么P 类属于NP类问题

答:P类问题是用确定的TM在多项式时间内可以求解的问题，

NP类问题是用确定的TM在多项式时间内可以验证的问题，可以求解的问题一定可以验证，而可以验证的问题不一定可以求解，

所以P类问题属于NP类问题。

问:NP类问题包含P类问题吗?为什么?

答:根据NP类问题的定义:NP表示确定的TM在多项式时间（步数）内可以验证的问题。

而P类问题表示确定的TM在多项式时间（步数）内可以求解的问题，由于可以被求解的问题一定可以被验证，

因此P类问题满足NP问题的定义，所以NP类包含P类。

如何证明P类问题包含于NP类问题中:

答:

P类问题是多项式时间内可以求解的问题，

而NP类问题是多项式时间内可以验证的问题，

因为凡是在多项式时间内可求解的问题则必然可以在多项式时间内验证，所以P类问题包含于NP类问题中。

问题:为什么说P⊆NP?

答案:P表示确定的TM在多项式时间（步数）内可判定的语言类，

NP表示不确定的TM在多项式时间（步数）内可判定的语言类，确定的TM是不确定的TM的特殊情况，

因此P⊆NP。

(四)差异

问题:P类问题和NP类问题的区别是?

回答:P类问题可验证可求算，NP类问题可验证不可求算，所以P类问题属于NP类问题。

问:Ｐ类和NP类问题的差别?

答:主要差别在于:

P类问题可以用多项式时间的确定性算法进行判定或求解

NP类问题可以用多项式时间的确定性算法来检查和验证它的解

问题:P类问题和NP类问题的差别?

答:P类问题可以用多项式时间的确定性算法进行判定或求解；NP类问题可以用多项式时间的确定性算法来检查和验证它的解

问题:Cook定理的意义是什么?

答:给出了第一个NP完全问题，使得对任何问题П，只要能证明П∈NP，且SAT∝pП，那么П是NPC问题。为NPC问题的发现奠定了基础。

P NP NPC NPH

判断:P问题属于NP问题，NPC 问题属于NP 问题。

答:正确。

问:一个问题是np问题但不是P类问题，那么它可能是什么问题?

答:npc问题。

P问题、NP问题与NPC问题三者关系如何?

答:NP完全问题是求NP中判定问题的一个子类．NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P＝NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。

问题:什么是NP完全问题?什么是P问题?什么是NP问题?

答案:

（1）NP完全（NP Complete，NPC）问题是指这样一类NP问题，所有的NP问题都可以用多项式时间划归到他们中的一个。

所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。

（2）P（Polynomial，多项式）问题．P问题是可以在多项式时间内被确定机（通常意义的计算机）解决的问题。

（3）NP（Non-Deterministic Polynomial， 非确定多项式）问题，是指可以在多项式时间内被非确定机解决的问题

问:分别阐述什么是P、NP、NPC、NPH问题?

答:

P: 能在多项式时间内解决的问题

NP: 不确定能不能在多项式时间内解决，但能在多项式时间验证的问题

NPC: NP完全问题，所有NP问题在多项式时间内都能约化（Reducibility）到这个NP问题，即解决了此NPC问题，所有NP问题也都得到解决。

NP hard:NP难问题，所有NP问题在多项式时间内都能约化（Reducibility）到这个问题（不一定是NP问题）。

问题:什么是P问题， 什么是NP问题， 什么是NP难度问题，什么是NP完全问题?

答:如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题．

NP问题是指可以在多项式的时间里验证一个解的问题．NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题．

NP-Hard问题:所有的NP问题都能规约到它，但它不一定是NP问题．

NP完全问题，也就是多项式复杂程度的非确定性问题．

NP hard问题的定义?

答:所有的np问题在多项式时间内都能约化到这个问题。该问题不一定是NP问题。

问题:P、NP、NPC、NP hard问题之间的关系是?

答:1． P问题属于NP问题，NPC问题属于NP问题。

2． NPC问题同时属于NP hard问题，是NP与NP hard的交集。

问:分别阐述什么是P、NP、NPC、NPH问题?

P: 能在多项式时间内解决的问题

NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验 证的问题

NPC: NP完全问题，所有NP问题在多项式时间内都能约化（Reducibility）到这个NP问题，即解决了此NPC问题，所有NP问题也都得到解决。

NP hard:NP难问题，所有NP问题在多项式时间内都能约化（Reducibility）到这个问题（不一定是NP问题）。

问:NP和NPH问题的关系?

答:互相并立，但也有公共部分，即NPC问题。

问题:NPC和NPH的差别?

回答:所有NP问题在多项式时间内都能约化到某个问题，若这个问题为NP问题，则为NPC，若不设限制（只要是问题，不一定是NP），则为NPH．

问题:什么是NP难度问题，什么是NP完全问题?

答:

NP难度问题:所有的NP问题都能规约到它，但它不一定是NP问题．

NP完全问题，也就是多项式复杂程度的非确定性问题．