 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 1263 | 回復(fù): 7 | ||
| 當(dāng)前只顯示滿足指定條件的回帖，點(diǎn)擊這里查看本話題的所有回帖 | ||
chentianyu1木蟲 (小有名氣)
|
[求助]
關(guān)于圖論問題的NP完備性證明
|
|
|
現(xiàn)在要證明一個圖論問題是NP-Complete，是否只需證明它對于某些特殊拓?fù)涞膱D（比如弦圖、二部圖）是NP-Complete的？如果答案是肯定的，請給出一個此類證明的例子。 個人感覺特殊拓?fù)涞膱D是NP-Complete不能說明這個問題就是NP-Complete，否則我們平時用NP-Complete來判別問題的復(fù)雜程度就沒意義了。 |
回復(fù)此樓» 猜你喜歡
299求調(diào)劑
已經(jīng)有8人回復(fù)
-
一志愿北京理工大學(xué)本科211材料工程294求調(diào)劑
已經(jīng)有6人回復(fù)
-
300求調(diào)劑，材料科學(xué)英一數(shù)二
已經(jīng)有8人回復(fù)
-
招收生物學(xué)/細(xì)胞生物學(xué)調(diào)劑
已經(jīng)有5人回復(fù)
-
070305高分子化學(xué)與物理 304分求調(diào)劑
已經(jīng)有7人回復(fù)
-
289求調(diào)劑
已經(jīng)有13人回復(fù)
-
一志愿哈爾濱工業(yè)大學(xué)材料與化工方向336分
已經(jīng)有9人回復(fù)
-
081200-11408-276學(xué)碩求調(diào)劑
已經(jīng)有6人回復(fù)
-
調(diào)劑求院校招收
已經(jīng)有5人回復(fù)
-
調(diào)劑310
已經(jīng)有8人回復(fù)
chentianyu1
木蟲 (小有名氣)
- 應(yīng)助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時
- 蟲號: 532712
- 注冊: 2008-03-25
- 性別: GG
- 專業(yè): 計(jì)算機(jī)網(wǎng)絡(luò)
3樓2012-11-11 18:34:22
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7791.4
- 散金: 574
- 紅花: 7
- 帖子: 1413
- 在線: 356.1小時
- 蟲號: 2101685
- 注冊: 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
|
《圖論》和《組合（數(shù)學(xué)）圖論》中的ＮＰ難題似乎比較多。 正在分析中：也許可以使用其中的一些ＮＰ難題用于設(shè)計(jì)非對稱加密解密算法。類似于ＲＳＡ等，非對稱加密解密算法主要是基于如：大數(shù)分解，離散對數(shù)，背包問題，以及橢圓曲線難題的。 一般有兩種辦法來證明某個問題是ＮＰ難的： １、非確定性圖靈機(jī)可驗(yàn)證的。 ２、可映射歸約到另一個ＮＰ難題。 例如，采用方法１來證明第一個被發(fā)現(xiàn)的ＮＰ難題：３－ＳＡＴ問題。它描述了：由多個三析取范式取合取， 例如：（Ｐ１或Ｐ２或Ｐ３）與（Ｐ２或Ｐ３或Ｐ５）……(p1 | p2 | p3) ^ (p2 | p3 |p5)……，看結(jié)果值是否為真值。 如果輸入Ｐ有２０個引腳，就有２^２０種可能，必須一個一個布爾函數(shù)去試； 如果輸入Ｐ有３０個引腳，就必須遍歷２^３０次來計(jì)算多個三析取范式是否的結(jié)果值是否為真值，同樣必須一個一個布爾函數(shù)去試。 它顯然是組合爆炸的。 在實(shí)際的布爾邏輯與安全的研究中，還明確了排列數(shù)Ｎ！甚至比指數(shù)２^Ｎ的計(jì)算量更大。 證明它是ＮＰ難題很簡單：給定一個例子，它是非確定性圖靈機(jī)可驗(yàn)證的。 |
2樓2012-11-11 18:01:33
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7791.4
- 散金: 574
- 紅花: 7
- 帖子: 1413
- 在線: 356.1小時
- 蟲號: 2101685
- 注冊: 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
4樓2012-11-11 18:50:02
chentianyu1
木蟲 (小有名氣)
- 應(yīng)助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時
- 蟲號: 532712
- 注冊: 2008-03-25
- 性別: GG
- 專業(yè): 計(jì)算機(jī)網(wǎng)絡(luò)
5樓2012-11-11 19:56:39
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 一志愿211 初試270分 求調(diào)劑 +8 | 谷雨上岸 2026-03-23 | 9/450 |
|
|---|---|---|---|---|
|
|
[碩博家園] 求調(diào)劑 330分 085600材料與化工 +3 | gqhhh 2026-03-22 | 3/150 |
|
|
[考研] 070300化學(xué)354求調(diào)劑 +3 | 101次希望 2026-03-28 | 3/150 |
|
|
|
[考研] 275求調(diào)劑 +10 | Micky11223 2026-03-25 | 14/700 |
|
|
|
[考研] 材料與化工272求調(diào)劑 +9 | 阿斯蒂芬2004 2026-03-28 | 9/450 |
|
|
|
[考研] 329求調(diào)劑 +6 | 星野? 2026-03-26 | 6/300 |
|
|
|
[考研] 一志愿南京航空航天大學(xué)材料學(xué)碩求調(diào)劑 +3 | @taotao 2026-03-28 | 3/150 |
|
|
|
[考研] 340求調(diào)劑 +5 | jhx777 2026-03-27 | 5/250 |
|
|
|
[考研] 275求調(diào)劑 +10 | jjjjjjjjjjl 2026-03-27 | 10/500 |
|
|
|
[考研] 298調(diào)劑 +3 | jiyingjie123 2026-03-27 | 3/150 |
|
|
|
[考研] 材料求調(diào)劑 +5 | .m.. 2026-03-25 | 5/250 |
|
|
|
[考研] 一志愿吉大071010，316分求調(diào)劑 +3 | xgbiknn 2026-03-27 | 3/150 |
|
|
|
[考研] 317求調(diào)劑 +7 | 蛋黃咸肉粽 2026-03-26 | 7/350 |
|
|
|
[考研] 342求調(diào)劑 +3 | 加油a李zs 2026-03-26 | 3/150 |
|
|
|
[考研] 294分080500材料科學(xué)與工程求調(diào)劑 +4 | 柳溪邊 2026-03-26 | 4/200 |
|
|
|
[考研] 0854AI CV方向招收調(diào)劑 +4 | 章小魚567 2026-03-23 | 4/200 |
|
|
|
[考研] 一志愿吉大化學(xué)322求調(diào)劑 +4 | 17501029541 2026-03-23 | 6/300 |
|
|
|
[考博] 26申博自薦 +3 | whh869393 2026-03-24 | 3/150 |
|
|
|
[考研] 341求調(diào)劑(一志愿湖南大學(xué)070300) +5 | 番茄頭--- 2026-03-22 | 6/300 |
|
|
|
[考研] 接收2026碩士調(diào)劑(學(xué)碩+專碩) +4 | allen-yin 2026-03-23 | 6/300 |
|