首页 >
NP完全
✍ dations ◷ 2025-08-26 04:33:01 #NP完全
NP完全或NP完备(NP-Complete,缩写为NP-C或NPC),是计算复杂度理论中,决定性问题的等级之一。NP完备是NP与NP困难的交集,是NP中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P(多项式时间可决定)的决定性问题的集合。若任何NPC问题得到多项式时间的解法,那此解法就可应用在所有NP问题上。更详细的定义容下叙述。一个NPC问题的例子是子集合加总问题,题目为这个问题的答案非常容易验证,但当前没有任何一个够快的方法可以在合理的时间内(意即多项式时间)找到答案。只能一个个将它的子集取出来一一测试,它的时间复杂度是
O
(
2
n
)
{displaystyle O(2^{n})}
,
n
{displaystyle n}
是此集合的元素数量。一个决定性问题C若是为NPC,则代表它对NP是完备的,这表示:可归约在此意指对每个问题L,总有一个多项式时间多对一变换,即一个决定性的算法可以将实例l ∈ L转化成实例c ∈ C,并让c回答Yes当且仅当此答案对l也是Yes。为了证明某个NP问题A实际上是NPC问题,证明者必须找出一个已知的NPC问题可以变换成A。本定义得到一个结论,就是若上述的C有一个多项式时间可解的算法,则我们可以将所有的NP问题降到P之中。这个定义是史提芬·古克所提出。虽然NPC这个词并没有出现在这篇论文上任何地方。在这个信息学会议上,信息学家激动地讨论NPC问题是否可以在一个确定型图灵机上以多项式时间求解。John Hopcroft总结与会众人的共识,认为由于没有人能对某一命题提出驳倒对方的证明,此问题不会于现在解决。此命题就是知名的一开始很难相信NPC问题是实际存在的,但著名的古克-李芬定理说明了一切(由Leonid Levin(英语:Leonid Levin)与Cook独立证出SAT问题是NPC问题,简化过但依旧艰深的证明在此)。在1972年,理查德·卡普证明有好几个问题也是NPC(请见卡普的二十一个NP-完全问题),因此除了SAT问题外,的确存在着一整类NPC问题。从古克开始,数千个问题借由从其他NPC问题变换而证实也是NPC问题,其中很多问题被搜集在Garey与Johnson于1979年出版的书之中。满足条件2(无论是否满足条件1)的问题集合被称为NP困难。一个NP困难问题至少跟NPC问题一样难。有一类问题已经被证明属于NP困难但不属于NP,即,这类问题至少与NP-complete一样难,但这类问题又不属于NP(自然也不属于NP-complete)。例如围棋的必胜下法,就是这样一个问题。另一个有趣的例是图同构(isomorphism)问题,即以图论方法决定两个图是否为同构。两图同构的直觉条件是若其中一图可以经由移动顶点使它与另一个图重合,则为同构。思考下列两问题:子图同构问题是NPC,而图同构问题一般认为不是P也不是NPC问题,虽然它明显是一个NP问题。这是一个典型被认为很难却还不是NPC问题的例子。想要证明一个问题是NPC,最简单的方法是先证明它属于NP,然后将“某个已知是NPC的问题”变换成它。因此在学习变换技巧前,先熟悉各种不同类型的NPC问题是很有用的。下表列出了一些以决定性命题表示的著名NPC问题:更多NPC问题的例子,请见NP-complete问题列表(英语:List of NP-complete problems)。右边是一些NPC问题及证明其为NPC问题的变换流程图。在流程图中,箭头代表的是从何问题变换成另一问题的过程,要注意的是这张图并不代表这些问题的数学关系,事实上任两个本质为NPC的问题都可以以多项式时间变换,这图仅指示可以让研究者较为简单地变换问题的顺序。通常一个P与NPC问题的叙述看起来只有一些不同的地方,例如3SAT问题(SAT问题的限制版本)仍然是NPC问题,但更限制的2SAT问题则是个P问题(准确的说,是NL-complete问题),而条件较为宽松的MAX 2SAT问题却又成了NPC问题。决定一个图是否能被两色涂满是P问题,但三色图是NPC问题,即使我们将它限制在平面图上。决定一个图有无循环或它是两分图很容易(在log空间等级),但是发现一个最大二分图或最大循环子图则是NPC。以一固定百分比来求郊游打包问题的最佳解可以在多项式时间解决,但是求最佳解是NPC。当前为止,所有已知解NPC问题的算法需要依照数据数量而定的超多项式(superpolynomial)时间,当前也不知道是否有任何更快的算法存在。因此要在输入数据量大的时候解决一个NPC问题,通常我们使用下列的手段来解:依照上述NPC的定义,所谓的变换其实是多项式时间多对一变换的简称。另一种化约法称为多项式时间图灵归约(polynomial-time Turing reduction(英语:polynomial-time Turing reduction))。若我们提供一个副函数(subroutine)可以在多项式时间解出"Y",又可写出调用此副函数的程序并在多项式时间解出问题"X",代表我们可以将"X"多项式时间图灵变换成"Y"。相较起来,不同处在于多对一变换只能调用上述副函数一次,且副函数的回传值必须就是整个变换程序回传的值。如果有人使用图灵变换而非多对一变换来解析NPC,此问题的解答集合不一定会小于NPC。孰大孰小其实是个开放问题。如果两个概念相同,则可导出NP=反NP(co-NP)。此结论成立的道理在于NPC与反NPC的定义以图灵归约来看是相等的,且图灵变换定义的NPC包含多对一变换定义的NPC,反NPC也是相同情况。所以若是两种变换定义的NPC一样大的话,反NPC也会比照办理(在两者的定义之下)。例如SAT的反问题也会是NPC(在两者的定义之下)。因此推得NP = 反NP(证明在反NP条目中)。虽然NP是否等于反NP是个开放问题,但一般认为这似乎不大可能,也因此那两类的NPC定义也不大可能相等。另一种很常用于NPC证明的变换手法是对数空间多对一变换(logarithmic-space many-one reduction),它是一种可以在对数量级空间运用的多对一变换法。由于每道可以在对数空间完成的运算也可以在多项式时间做完,因此能使用对数空间多对一变换的场合也可以使用多项式时间多对一变换。本方法较多项式时间多对一变换优雅,它也可以让我们对算法复杂度细分出更多分类,例如P完备复杂度。而NPC的定义是否会因为使用不同变换手法而产生差异,仍是一个未知的问题。
相关
- 老人医学人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学老年医学(英语:Geriatrics)是医学的一个
- 同种型免疫球蛋白的同种型是指免疫球蛋白类型或亚型的重链遗传变化或差异。人类有九种同种型:免疫球蛋白类型转换可以改变重链的类型,但不会改变轻链。表位(线性、构象)抗体(单株抗体、
- 平民保育团平民保育团(Civilian Conservation Corps,CCC)是美国在1933年至1942年间,对19至24岁的单身救济户失业男性推行的以工代赈计划,这些救济户都是在经济大萧条期间失业、难以找到工作
- 柑橘柑橘是芸香科柑橘属水果的统称。主要种类有橘、柑、甜橙、酸橙、柚、葡萄柚、柠檬、莱姆、枸橼、佛手柑和金橘等。柑橘类水果是世界上产量最大的水果,目前的年产量已经超过了
- 切割蛋白酶解或蛋白水解(英语:Proteolysis)是指蛋白质降解为较小的多肽或氨基酸的过程。通常情况下,被水解的都是肽键,且在蛋白酶的作用下进行,因此常用蛋白酶解。但也可能发生分子内
- 亚显微细胞结构亚显微结构,又称超微结构,是指在普通光学显微镜下无法分辨的各种微细结构。根据阿贝理论,普通光学显微镜的分辨率极限为~200纳米,也就是说如果所观测物体的尺寸在200纳米附近或小
- 嫩肉粉木瓜蛋白酶(英语:papain),或简称木瓜酶、木瓜酵素,又称嫩精或木瓜粉,是存在于番木瓜果实中的一种半胱氨酸蛋白酶。木瓜蛋白酶对于嫩化肉类起着重要作用,市面上更多称为松肉粉或嫩肉
- 线粒体嵴1 线粒体外膜 2 膜间隙5 内层11 线粒体 DNA 12 基质颗粒 13 核糖体 14 ATP 合酶 15 孔蛋白线粒体嵴(英语:mitochondrial cristae)简称“嵴”,是线粒体内膜向线粒体基质折褶形成
- 先驱者计划name = 'Aero', description = '航空太空科技(航空航天科技)', content = {{ type = 'text', text = [=[本页面没有类似于NoteTA的数量限制。 请自行修改分类名。在NoteTA样板
- 百科全书《百科全书,或科学、艺术和工艺详解词典》(法语:Encyclopédie, ou dictionnaire raisonné des sciences, des arts et des métiers),通称《百科全书》(Encyclopédie),是1751年至