1,合取范式问题(leproblemeSAT－satisfaisatilite)
2,三元合取范式问题(leprobleme3-SAT)
3,？？？？(leproblemeM3D－mariagetri-dimensionnel)
4,顶点涵盖问题(leproblemeRS－recouvrementdessommet)
5,分团问题(leproblemeCL－clique)
6,汉弥尔顿循环问题(leproblemeCH－circuithamiltonien)
7,NPC变换流程图(leproblemePART－partition)
[
阅读全文]
ListofNP-completeproblemsFromWikipedia,thefreeencyclopediaJumpto:navigation,searchHerearesomeofthemorecommonlyknownproblemsthatareNP-completewhenexpressedasdecisionproblems.Thislistisinnowaycomprehensive(therearemorethan3000knownNP-completeproblems).MostoftheproblemsinthislistaretakenfromGareyandJohnson'sseminalbookComputersandIntractability:AGuidetotheTheoryofNP-Completeness,andareherepresentedin...[
阅读全文]
ListedeproblèmesNP-completsUnarticledeWikipédia,l'encyclopédielibre.Allerà:Navigation,RechercherCeciestunelistedesproblèmesNP-completslesplusconnusenthéoriedelacomplexité,expriméssouslaformed'unproblèmesdeladécision.Puisqu'onconnaîtplusde3000problèmesNP-complets,cettelisten'estpasexhaustive.LaplupartdesproblèmesénumérésproviennentdulivrefondamentaldeGareyetJohnson:Computersand...[
阅读全文]
反证法。设P=NP。令y为一个P=NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P=NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。[
阅读全文]
PNPNPC问题
1。基本概念：问题复杂度和算法复杂度；具体问题和抽象问题；判定性问题；
2。编码对问题解决效率的影响（效率与编码方式的依赖性相当严重），多项式相关编码，多项式时间可计算函数；
3。复杂类P
Apolynomiallyboundedalgorithmisonewithitsworst-casecomplexityboundedbyapolynonialfunctionoftheinputsize.
Apolynoniallyboundedproblemisoneforwhichthereisapolynomiallybounde...[
阅读全文]
演讲视频下载地址：URL:mms://winmedia.cctv.com/wwwwxinwen/2007/12/wwwwxinwen_300_20071228_47.wmv可用迅雷下载。[
阅读全文]
