 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 8 | 1/1 | 返回列表 |
| 查看: 1254 | 回復(fù): 7 | |||
chentianyu1木蟲 (小有名氣)
|
[求助]
關(guān)于圖論問題的NP完備性證明
|
|
現(xiàn)在要證明一個圖論問題是NP-Complete，是否只需證明它對于某些特殊拓撲的圖（比如弦圖、二部圖）是NP-Complete的？如果答案是肯定的，請給出一個此類證明的例子。 個人感覺特殊拓撲的圖是NP-Complete不能說明這個問題就是NP-Complete，否則我們平時用NP-Complete來判別問題的復(fù)雜程度就沒意義了。 |
回復(fù)此樓» 猜你喜歡
材料專業(yè)求調(diào)劑
已經(jīng)有7人回復(fù)
-
材料專碩英一數(shù)二306
已經(jīng)有8人回復(fù)
-
一志愿河北工業(yè)大學(xué)0817化工278分求調(diào)劑
已經(jīng)有6人回復(fù)
-
請教下大家 2026年國家基金申請是雙盲審嗎？
已經(jīng)有4人回復(fù)
-
一志愿南航材料專317分求調(diào)劑
已經(jīng)有3人回復(fù)
-
環(huán)境學(xué)碩288求調(diào)劑
已經(jīng)有7人回復(fù)
-
一志愿華東理工大學(xué)081700，初試分數(shù)271
已經(jīng)有4人回復(fù)
-
一志愿重慶大學(xué)085700資源與環(huán)境，總分308求調(diào)劑
已經(jīng)有8人回復(fù)
-
化學(xué)308分求調(diào)劑
已經(jīng)有3人回復(fù)
-
085600材料與化工調(diào)劑
已經(jīng)有11人回復(fù)
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7786.4
- 散金: 574
- 紅花: 7
- 帖子: 1412
- 在線: 356.1小時
- 蟲號: 2101685
- 注冊: 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
|
《圖論》和《組合（數(shù)學(xué)）圖論》中的ＮＰ難題似乎比較多。 正在分析中：也許可以使用其中的一些ＮＰ難題用于設(shè)計非對稱加密解密算法。類似于ＲＳＡ等，非對稱加密解密算法主要是基于如：大數(shù)分解，離散對數(shù)，背包問題，以及橢圓曲線難題的。 一般有兩種辦法來證明某個問題是ＮＰ難的： １、非確定性圖靈機可驗證的。 ２、可映射歸約到另一個ＮＰ難題。 例如，采用方法１來證明第一個被發(fā)現(xiàn)的ＮＰ難題：３－ＳＡＴ問題。它描述了：由多個三析取范式取合取， 例如：（Ｐ１或Ｐ２或Ｐ３）與（Ｐ２或Ｐ３或Ｐ５）……(p1 | p2 | p3) ^ (p2 | p3 |p5)……，看結(jié)果值是否為真值。 如果輸入Ｐ有２０個引腳，就有２^２０種可能，必須一個一個布爾函數(shù)去試； 如果輸入Ｐ有３０個引腳，就必須遍歷２^３０次來計算多個三析取范式是否的結(jié)果值是否為真值，同樣必須一個一個布爾函數(shù)去試。 它顯然是組合爆炸的。 在實際的布爾邏輯與安全的研究中，還明確了排列數(shù)Ｎ！甚至比指數(shù)２^Ｎ的計算量更大。 證明它是ＮＰ難題很簡單：給定一個例子，它是非確定性圖靈機可驗證的。 |
2樓2012-11-11 18:01:33
chentianyu1
木蟲 (小有名氣)
- 應(yīng)助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時
- 蟲號: 532712
- 注冊: 2008-03-25
- 性別: GG
- 專業(yè): 計算機網(wǎng)絡(luò)
3樓2012-11-11 18:34:22
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7786.4
- 散金: 574
- 紅花: 7
- 帖子: 1412
- 在線: 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è): 計算機網(wǎng)絡(luò)
5樓2012-11-11 19:56:39
emmett08
金蟲 (正式寫手)
- 應(yīng)助: 17 (小學(xué)生)
- 金幣: 2958.8
- 散金: 2432
- 紅花: 8
- 帖子: 426
- 在線: 368.6小時
- 蟲號: 1945437
- 注冊: 2012-08-19
- 性別: GG
- 專業(yè): 模式識別
6樓2012-11-12 20:47:32
zhongyantao
鐵蟲 (著名寫手)
- 應(yīng)助: 3 (幼兒園)
- 金幣: 810.8
- 散金: 80
- 紅花: 3
- 帖子: 1062
- 在線: 275.7小時
- 蟲號: 2052020
- 注冊: 2012-10-09
- 專業(yè): 信息安全
7樓2012-12-08 11:16:30
8樓2013-03-25 21:21:43
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 chentianyu1 的主題更新
| 8 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[基金申請] 請教下大家 2026年國家基金申請是雙盲審嗎？ +3 | lishucheng1 2026-03-22 | 4/200 |
|
|---|---|---|---|---|
|
[考研] 一志愿重慶大學(xué)085700資源與環(huán)境，總分308求調(diào)劑 +7 | 墨墨漠 2026-03-23 | 8/400 |
|
|
|
[考研] 求調(diào)劑一志愿武漢理工大學(xué)材料工程（085601） +3 | WW.' 2026-03-23 | 5/250 |
|
|
|
[考研] 350求調(diào)劑 +6 | weudhdk 2026-03-19 | 6/300 |
|
|
|
[考研] 081700 調(diào)劑 267分 +5 | 迷人的哈哈 2026-03-23 | 5/250 |
|
|
|
[考研] 298求調(diào)劑一志愿211 +3 | 上岸6666@ 2026-03-20 | 3/150 |
|
|
|
[考研] 278求調(diào)劑 +9 | 煙火先于春 2026-03-17 | 9/450 |
|
|
|
[考研] 313求調(diào)劑 +4 | 肆叁貳壹22 2026-03-19 | 4/200 |
|
|
|
[考研] 332求調(diào)劑 +3 | 鳳凰院丁真 2026-03-20 | 3/150 |
|
|
|
[考研] 085601調(diào)劑 358分 +3 | zzzzggh 2026-03-20 | 4/200 |
|
|
|
[考研] 307求調(diào)劑 +3 | wyyyqx 2026-03-17 | 3/150 |
|
|
|
[考研] 材料 336 求調(diào)劑 +3 | An@. 2026-03-18 | 4/200 |
|
|
|
[考研] 一志愿武理材料305分求調(diào)劑 +6 | 想上岸的鯉魚 2026-03-18 | 7/350 |
|
|
|
[考研] 22408 344分 求調(diào)劑 一志愿 華電計算機技術(shù) +4 | solanXXX 2026-03-20 | 4/200 |
|
|
|
[考研] 308求調(diào)劑 +3 | 阿姐阿姐家啊 2026-03-18 | 3/150 |
|
|
|
[考研] 329求調(diào)劑 +9 | 想上學(xué)吖吖 2026-03-19 | 9/450 |
|
|
|
[考研] 086500 325 求調(diào)劑 +3 | 領(lǐng)帶小熊 2026-03-19 | 3/150 |
|
|
|
[考研] 廣西大學(xué)家禽遺傳育種課題組2026年碩士招生（接收計算機專業(yè)調(diào)劑） +3 | 123阿標 2026-03-17 | 3/150 |
|
|
|
[考博] 申博26年 +3 | 八6八68 2026-03-19 | 3/150 |
|
|
|
[考研] 【同濟軟件】軟件（085405）考研求調(diào)劑 +3 | 2026eternal 2026-03-18 | 3/150 |
|