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可用迅雷下載。[
閱讀全文]
