当前位置:主页 > 金沙js网站 > 正文

P有什么问题?NP有什么问题?NPC有什么问题?这

2019-04-03 来源:网络整理 责任编辑:互联网 点击:

展开全部
问题P是一种决策问题,可以使用确定性算法在多项式时间内确定或求解。
如果确定性问题的复杂性是问题实例大小的多项式函数,则可以在多项式时间内求解的这个确定性问题被认为属于类型P的问题。
类型P问题是所有复杂问题的集合,例如多项式时间。
NP是一种决策问题。这些问题可以通过确定的算法在多项式时间内验证或验证。事实上,P非常直观。我们通常在编程中解决的大多数问题都是P型问题。
例如,排序,搜索最短路径等。
2,NP问题但是用多项式时间算法很难找到一些问题,例如在无向图中发现哈密顿环的问题(它们可能不存在),但我们回答这个问题如果给出问题,您可以确定在多项式时间内答案是否正确。
例如,在Hamilton循环问题中,很容易确定它是否是任何循环的Hamilton循环(仅参见所有顶点都在循环中)。
在多项式时间内验证解是正确的这个问题被称为NP问题。
显然,所有P型问题都与NP有关,但现在的问题是:
这个问题还没有解决。
NP课非常有趣。它不需要算法来解决问题本身,而只需要确定性算法来在多项式时间内验证其解。
3,NP完全问题另外,请注意NP问题并不总是困难的问题。例如,简单矩阵分类的问题是P型问题,但P属于NP。这是一个NP问题,你能说它很难解决吗?
目前,我不知道是否有P = NP或PNP,但后来我发现有一些特殊的NP问题。这些问题的特殊性使许多人相信PNP,但现在无法证明。
特别是,这个NP的问题是完美NP的问题(NPC的问题,C意味着完美)。
完整的NP问题是NP问题的子类。
人大问题具有令人惊讶的性质。如果NPC问题具有多项式时间算法,那么所有NP问题都可以在多项式时间内求解。那是吗?设定P = NP。
这是因为每个NPC问题可以在多项式时间内转换为任何NP问题。
例如,上述Hamilton循环问题是NPC问题。
人大问题的历史并不古老。库克在1971年发现了第一个NPC问题。从那以后,人们遇到了很多人大问题,现在可能有3000多人。
因此,我认为NPC问题通常是一个难题,因为不太可能存在NPC问题的多项式时间算法(如果所有NP问题都存在多项式时间算法,那么它并不令人难以置信但不可能)。
汉密尔顿的路径/轨道问题,供应商问题,群体问题,最小边缘覆盖问题(注意力和路线覆盖之间的差异)以及许多其他问题都是NPC,因此很难解决它们。