族谱网 头条 人物百科

完全

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:514
转发:0
评论:0
NPC的正式定义假设P≠NP的复杂度类的图解。若P=NP则三类别相同。一个决定性问题C若是为NPC,则代表它对NP是完备的,这表示:它是一个NP问题,且其他属于NP的问题都可归约成它。可归约在此意指对每个问题L,总有一个多项式时间多对一变换,即一个决定性的算法可以将实例l∈L转化成实例c∈C,并让c回答Yes当且仅当此答案对l也是Yes。为了证明某个NP问题A实际上是NPC问题,证明者必须找出一个已知的NPC问题可以变换成A。本定义得到一个结论,就是若上述的C有一个多项式时间可解的算法,则我们可以将所有的NP问题降到P之中。这个定义是史提芬·古克所提出。虽然NPC这个词并没有出现在这篇论文上任何地方。在这个信息学会议上,信息学家激动地讨论NPC问题是否可以在一个确定型图灵机上以多项式时间求解。JohnHopcroft总结与会众人的共识,认为由于没有人能对某一命题提出驳倒对方的证明,此问题不

C的正式定义

完全

  假设 P ≠ 的复杂度类的图解。若 P = 则三类别相同。

一个决定性问题 C 若是为C,则代表它对是完备的,这表示:

它是一个问题,且

其他属于的问题都可归约成它。

可归约 在此意指对每个问题 L ,总有一个多项式时间多对一变换,即一个决定性的算法可以将实例 l ∈ L 转化成实例 c ∈ C ,并让 c 回答Yes当且仅当此答案对 l 也是Yes。为了证明某个问题 A 实际上是C问题,证明者必须找出一个已知的C问题可以变换成 A 。

本定义得到一个结论,就是若上述的 C 有一个多项式时间可解的算法,则我们可以将所有的问题降到P之中。

这个定义是史提芬·古克 所提出。虽然C这个词并没有出现在这篇论文上任何地方。在这个信息学会议上,信息学家激动地讨论C问题是否可以在一个确定型图灵机上以多项式时间求解。John Hopcroft总结与会众人的共识,认为由于没有人能对某一命题提出驳倒对方的证明,此问题不会于现在解决。此命题就是知名的

一开始很难相信C问题是实际存在的,但著名的古克-李芬定理说明了一切(由Leonid Levin与Cook独立证出SAT问题是C问题,简化过但依旧艰深的证明在此)。

在1972年,Richard Karp证明有好几个问题也是C(请见卡普的二十一个-完全问题),因此除了SAT问题外,的确存在着一整类C问题。从古克开始,数千个问题借由从其他C问题变换而证实也是C问题,其中很多问题被搜集在Garey与Johnson于1979年出版的书之中 。

满足条件2(无论是否满足条件1)的问题集合被称为-hard。一个-hard问题至少跟C问题一样难。有一类问题已经被证明属于-hard但不属于,即,这类问题至少与-complete一样难,但这类问题又不属于(自然也不属于-complete)。例如围棋的必胜下法,就是这样一个问题。

示例问题

另一个有趣的例是图同构(isomorphism)问题,即以图论方法决定两个图是否为同构。两图同构的直觉条件是若其中一图可以经由移动顶点使它与另一个图重合,则为同构。思考下列两问题:

图同构:图G 1 是否与图G 2 同构?

子图同构:图G 1 是否与图G 2 的 任一子图 同构?

子图同构问题是C,而图同构问题一般认为不是P也不是C问题,虽然它明显是一个问题。这是一个典型被认为很难却还不是C问题的例子。

想要证明一个问题是C,最简单的方法是先证明它属于,然后将“某个已知是C的问题”变换成它。因此在学习变换技巧前,先熟悉各种不同类型的C问题是很有用的。下表列出了一些以决定性命题表示的著名C问题:

完全

  变换流程图。

布尔可满足性问题

N-puzzle问题(华容道问题)

背包问题

汉弥尔顿循环问题

旅行推销员问题

子图同构问题:(Subgraph isomorphism problem)

子集合加总问题

分团问题

顶点涵盖问题

独立顶点集问题:(Independent set problem)

图着色问题

扫雷

更多C问题的例子,请见-complete问题列表(英文版)。

右边是一些C问题及证明其为C问题的变换流程图。在流程图中,箭头代表的是从何问题变换成另一问题的过程,要注意的是这张图并不代表这些问题的数学关系,事实上任两个本质为C的问题都可以以多项式时间变换,这图仅指示可以让研究者较为简单地变换问题的顺序。

通常一个P与C问题的叙述看起来只有一些不同的地方,例如3SAT问题(SAT问题的限制版本)仍然是C问题,但更限制的2SAT问题则是个P问题(准确的说,是NL-complete问题),而条件较为宽松的MAX 2SAT问题却又成了C问题。决定一个图是否能被两色涂满是P问题,但三色图是C问题,即使我们将它限制在平面图上。决定一个图有无循环或它是两分图很容易(在log空间档次),但是发现一个最大二分图或最大循环子图则是C。以一固定百分比来求郊游打包问题的最佳解可以在多项式时间解决,但是求最佳解是C。

折衷的解法

目前为止,所有已知解C问题的算法需要依照数据数量而定的 超多项式 (superpolynomial)时间,目前也不知道是否有任何更快的算法存在。因此要在输入数据量大的时候解决一个C问题,通常我们使用下列的手段来解:

近似算法:这类算法可以快速发现离最佳解在一定差距内的次佳解。

随机数算法:此类算法可提供一随机数产生的输入数据,让 本质上解答分布均匀 的受测程序可以有良好的求解效率。对于解答分布不均匀的程序,则可以降低随机数程度以改变输入数据。

特例:此算法可以在题目呈献某些特殊情况时快速得解。参数化复杂度(Parameterized complexity)可视为广义的此类算法。

启发式算法:这种算法在许多时候可以产生 理性解答 (即运用评比或线索找出解),但无法保证它效率的良莠与解答的好坏程度。一个启发式算法的例子是用在图着色问题以O( n log n )的贪婪算法找次佳解,用在某些编译器的寄存器配置阶段上,此技术又叫图着色全域寄存器配置(graph-coloring global register allocation)。每顶点视为一变量,每边代表两变量同时使用的情况,颜色则代表配置给每一变量的寄存器编号。由于大多数的RISC机器拥有大量通用寄存器,因此启发式算法很适合用来解这类题目。

其他变换法

依照上述C的定义,所谓的变换其实是多项式时间多对一变换的简称。

另一种化约法称为多项式时间图灵归约(polynomial-time Turing reduction)。若我们提供一个副函数(subroutine)可以在多项式时间解出"Y", 又 可写出调用此副函数的程序并在多项式时间解出问题"X",代表我们可以将"X"多项式时间图灵变换成"Y"。相较起来,不同处在于多对一变换只能调用上述副函数 一次 ,且副函数的回传值必须 就是 整个变换程序回传的值。

如果有人使用图灵变换而非多对一变换来解析C,此问题的解答集合不一定会小于C。孰大孰小其实是个开放问题。如果两个概念相同,则可导出=反(co-)。此结论成立的道理在于C与反C的定义以图灵归约来看是相等的,且图灵变换定义的C包含多对一变换定义的C,反C也是相同情况。所以若是两种变换定义的C一样大的话,反C也会比照办理(在两者的定义之下)。例如SAT的反问题也会是C(在两者的定义之下)。因此推得 = 反(证明在反条目中)。虽然是否等于反是个开放问题,但一般认为这似乎不大可能,也因此那两类的C定义也不大可能相等。

另一种很常用于C证明的变换手法是对数空间多对一变换(logarithmic-space many-one reduction),它是一种可以在对数量级空间运用的多对一变换法。由于每道可以在对数空间完成的运算也可以在多项式时间做完,因此能使用对数空间多对一变换的场合也可以使用多项式时间多对一变换。本方法较多项式时间多对一变换优雅,它也可以让我们对算法复杂度细分出更多分类,例如P完备复杂度。而C的定义是否会因为使用不同变换手法而产生差异,仍是一个未知的问题。


 


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 完全比赛
美国大联盟的完全比赛19世纪现代注:在最早的两场完全比赛发生的当时,投手只能用低手投球(手不能高过腰带),投手板和本垒板的距离是45英尺,保送要8个坏球,打者可以指定高球或低球等等。它们基本上跟名单里的其他比赛不一样,所以把它们列进名单总是引起广泛地讨论。在赛·扬的完全比赛之后的规则改变就没有那么显著了。赛·扬的完全比赛是连续无安打局数(24局,尚未被打破)和连续无失分局数(45局,已被打破)的一部分。唐·拉森在1956年世界大赛第五场所投出的完全比赛,是第一场也是唯一一场季后赛里的完全比赛,还是第一场季后赛里的无安打比赛,第二场季后赛无安打比赛是由洛伊·哈勒戴于2010年10月6日对上红人的比赛中投出。在山迪·柯法斯所投出的完全比赛里,对手芝加哥小熊的投手BobHendley只被击出一支安打,是第七局里的一支二垒德州安打,而且留下了二垒的残垒。洛杉矶道奇所得的唯一一分是在第五局得到的。致...
· 完全数
完全数的发现古希腊数学家欧几里得是通过2n−−-->1××-->(2n−−-->1){\displaystyle2^{n-1}\times(2^{n}-1)}的表达式发现前四个完全数的。一个偶数是完美数,当且仅当它具有如下形式:2n−−-->1(2n−−-->1){\displaystyle2^{n-1}(2^{n}-1)},其中2n−−-->1{\displaystyle2^{n}-1}是素数,此事实的充分性由欧几里得欧拉,而必要性则由欧拉所证明。比如,上面的6和28对应着n=2和3的情况。我们只要找到了一个形如2−1的素数(即梅森素数),也就知道了一个偶完美数。尽管没有发现奇完全数,但是当代数学家奥斯丁·欧尔证明,若有奇完全数,则其形式必然是12p+1{\displaystyle12p+1}或36p+9{\dis...
· 半完全数
参见高合成数完全数婚约数亲和数丰数亏数梅森素数佩服数
· 完全是真的
“那真是一件可怕的事情!”母鸡说。她讲这话的地方不是城里发生这个故事的那个区域。“那是鸡屋里的一件可怕的事情!我今夜不敢一个人睡觉了!真是幸运,我们今晚大伙儿都栖在一根栖木上!”于是她讲了一个故事,弄得别的母鸡羽毛根根竖起,而公鸡的冠却垂下来了。这完全是真的!不过我们还是从头开始吧。事情是发生在城里另一区的鸡屋里面。太阳落下了,所有的母鸡都飞上了栖木。有一只母鸡,羽毛很白,腿很短;她总是按规定的数目下蛋。在各方面说起来,她是一只很有身份的母鸡。当她飞到栖木上去的时候,她用嘴啄了自己几下,弄得有一根小羽毛落下来了。“事情就是这样!”她说,“我越把自己啄得厉害,我就越漂亮!”她说这话的神情是很快乐的,因为她是母鸡中一个心情愉快的人物,虽然我刚才说过她是一只很有身份的鸡。不久她就睡着了。周围是一起漆黑。母鸡跟母鸡站在一边,不过离她最近的那只母鸡却睡不着。她在静听——一只耳朵进,一只耳朵出;一个人...
· 完全非弹性碰撞
参阅碰撞弹性碰撞非弹性碰撞恢复系数

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信