 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1269 | 回復: 7 | ||
| 當前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | ||
chentianyu1木蟲 (小有名氣)
|
[求助]
關于圖論問題的NP完備性證明
|
|
|
現在要證明一個圖論問題是NP-Complete，是否只需證明它對于某些特殊拓撲的圖（比如弦圖、二部圖）是NP-Complete的？如果答案是肯定的，請給出一個此類證明的例子。 個人感覺特殊拓撲的圖是NP-Complete不能說明這個問題就是NP-Complete，否則我們平時用NP-Complete來判別問題的復雜程度就沒意義了。 |
回復此樓» 猜你喜歡
08工科275分求調劑
已經有3人回復
-
288求調劑 一志愿哈工大 材料與化工
已經有14人回復
-
安徽大學專碩生物與醫(yī)藥專業(yè)(086000)324分，英語已過四六級，六級521，求調劑
已經有11人回復
-
070300化學求調劑
已經有12人回復
-
化學308分調劑
已經有12人回復
-
359求調劑
已經有3人回復
-
一志愿武理材料工程302調劑環(huán)化或化工
已經有8人回復
-
材料工程085601數二英一335求調劑
已經有5人回復
-
一志愿北京科技大學材料學碩328分求調劑
已經有3人回復
-
0856求調劑
已經有9人回復
zhongyantao
鐵蟲 (著名寫手)
- 應助: 3 (幼兒園)
- 金幣: 810.8
- 散金: 80
- 紅花: 3
- 帖子: 1062
- 在線: 275.7小時
- 蟲號: 2052020
- 注冊: 2012-10-09
- 專業(yè): 信息安全
7樓2012-12-08 11:16:30
ftai
金蟲 (著名寫手)
- 應助: 19 (小學生)
- 金幣: 7791.4
- 散金: 574
- 紅花: 7
- 帖子: 1413
- 在線: 356.1小時
- 蟲號: 2101685
- 注冊: 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
|
《圖論》和《組合（數學）圖論》中的ＮＰ難題似乎比較多。 正在分析中：也許可以使用其中的一些ＮＰ難題用于設計非對稱加密解密算法。類似于ＲＳＡ等，非對稱加密解密算法主要是基于如：大數分解，離散對數，背包問題，以及橢圓曲線難題的。 一般有兩種辦法來證明某個問題是ＮＰ難的： １、非確定性圖靈機可驗證的。 ２、可映射歸約到另一個ＮＰ難題。 例如，采用方法１來證明第一個被發(fā)現的ＮＰ難題：３－ＳＡＴ問題。它描述了：由多個三析取范式取合取， 例如：（Ｐ１或Ｐ２或Ｐ３）與（Ｐ２或Ｐ３或Ｐ５）……(p1 | p2 | p3) ^ (p2 | p3 |p5)……，看結果值是否為真值。 如果輸入Ｐ有２０個引腳，就有２^２０種可能，必須一個一個布爾函數去試； 如果輸入Ｐ有３０個引腳，就必須遍歷２^３０次來計算多個三析取范式是否的結果值是否為真值，同樣必須一個一個布爾函數去試。 它顯然是組合爆炸的。 在實際的布爾邏輯與安全的研究中，還明確了排列數Ｎ！甚至比指數２^Ｎ的計算量更大。 證明它是ＮＰ難題很簡單：給定一個例子，它是非確定性圖靈機可驗證的。 |
2樓2012-11-11 18:01:33
chentianyu1
木蟲 (小有名氣)
- 應助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時
- 蟲號: 532712
- 注冊: 2008-03-25
- 性別: GG
- 專業(yè): 計算機網絡
3樓2012-11-11 18:34:22
ftai
金蟲 (著名寫手)
- 應助: 19 (小學生)
- 金幣: 7791.4
- 散金: 574
- 紅花: 7
- 帖子: 1413
- 在線: 356.1小時
- 蟲號: 2101685
- 注冊: 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
4樓2012-11-11 18:50:02
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 材料工程085601數二英一335求調劑 +5 | 雙馬尾痞老板2 2026-03-31 | 5/250 |
|
|---|---|---|---|---|
|
|
[考研] 一志愿華東師范大學有機化學專業(yè)，初試351分，復試被刷求調劑! +9 | 真名有冰 2026-03-29 | 10/500 |
|
|
[考研] 263求調劑 +3 | DDDDuu 2026-03-27 | 3/150 |
|
|
|
[考研] 本科211生物醫(yī)學工程085409求調劑339分 +7 | 里子木yy 2026-03-29 | 7/350 |
|
|
|
[考研] 334求調劑 +7 | Trying] 2026-03-31 | 7/350 |
|
|
|
[考研] 287求調劑 +17 | land xuxu 2026-03-26 | 17/850 |
|
|
|
[考研] 085600材料與化工調劑 +16 | kikiki7 2026-03-30 | 16/800 |
|
|
|
[考研] 083000環(huán)境科學與工程調劑，總分281 +4 | 橙子（勝意） 2026-03-30 | 4/200 |
|
|
|
[考研] 一志愿北京化工大學材料與化工（085600）296求調劑 +25 | 稻妻小編 2026-03-26 | 25/1250 |
|
|
|
[考研] 292求調劑 +13 | 是妍子也是研子 2026-03-30 | 13/650 |
|
|
|
[考研] 334分 一志愿武理 材料求調劑 +16 | 李李不服輸 2026-03-26 | 16/800 |
|
|
|
[考研] 324求調劑 +9 | hanamiko 2026-03-26 | 11/550 |
|
|
|
[考研] 生物技術與工程 +7 | 1294608413 2026-03-25 | 8/400 |
|
|
|
[考研] 295求調劑 +5 | wei-5 2026-03-26 | 5/250 |
|
|
|
[考研] 356求調劑 +4 | gysy?s?a 2026-03-28 | 4/200 |
|
|
|
[考研] 312，生物學求調劑 +3 | 小譯同學abc 2026-03-28 | 3/150 |
|
|
|
[考研] 085600，材料與化工321分，求調劑 +9 | 大饞小子 2026-03-27 | 9/450 |
|
|
|
[考研] 309求調劑 +4 | gajsj 2026-03-25 | 5/250 |
|
|
|
[考研] 302求調劑 +4 | 錦衣衛(wèi)藤椒 2026-03-25 | 4/200 |
|
|
|
[考研] 各位老師您好：本人初試372分 +5 | jj涌77 2026-03-25 | 6/300 |
|