 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 8 | 1/1 | 返回列表 |
| 查看: 1253 | 回復(fù): 7 | ||
chentianyu1木蟲 (小有名氣)
|
[求助]
關(guān)于圖論問(wèn)題的NP完備性證明
|
|
現(xiàn)在要證明一個(gè)圖論問(wèn)題是NP-Complete，是否只需證明它對(duì)于某些特殊拓?fù)涞膱D（比如弦圖、二部圖）是NP-Complete的？如果答案是肯定的，請(qǐng)給出一個(gè)此類證明的例子。 個(gè)人感覺特殊拓?fù)涞膱D是NP-Complete不能說(shuō)明這個(gè)問(wèn)題就是NP-Complete，否則我們平時(shí)用NP-Complete來(lái)判別問(wèn)題的復(fù)雜程度就沒意義了。 |
回復(fù)此樓» 猜你喜歡
一志愿陜師大生物學(xué)071000，298分，求調(diào)劑
已經(jīng)有3人回復(fù)
-
306求0703調(diào)劑一志愿華中師范
已經(jīng)有7人回復(fù)
-
333求調(diào)劑
已經(jīng)有3人回復(fù)
-
335求調(diào)劑
已經(jīng)有4人回復(fù)
-
336求調(diào)劑
已經(jīng)有4人回復(fù)
-
303求調(diào)劑
已經(jīng)有4人回復(fù)
-
085600材料與化工調(diào)劑
已經(jīng)有6人回復(fù)
-
291求調(diào)劑
已經(jīng)有5人回復(fù)
-
0703化學(xué)求調(diào)劑
已經(jīng)有4人回復(fù)
-
07化學(xué)280分求調(diào)劑
已經(jīng)有3人回復(fù)
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7786.4
- 散金: 574
- 紅花: 7
- 帖子: 1412
- 在線: 356.1小時(shí)
- 蟲號(hào): 2101685
- 注冊(cè): 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
|
《圖論》和《組合（數(shù)學(xué)）圖論》中的ＮＰ難題似乎比較多。 正在分析中：也許可以使用其中的一些ＮＰ難題用于設(shè)計(jì)非對(duì)稱加密解密算法。類似于ＲＳＡ等，非對(duì)稱加密解密算法主要是基于如：大數(shù)分解，離散對(duì)數(shù)，背包問(wèn)題，以及橢圓曲線難題的。 一般有兩種辦法來(lái)證明某個(gè)問(wèn)題是ＮＰ難的： １、非確定性圖靈機(jī)可驗(yàn)證的。 ２、可映射歸約到另一個(gè)ＮＰ難題。 例如，采用方法１來(lái)證明第一個(gè)被發(fā)現(xiàn)的ＮＰ難題：３－ＳＡＴ問(wèn)題。它描述了：由多個(gè)三析取范式取合取， 例如：（Ｐ１或Ｐ２或Ｐ３）與（Ｐ２或Ｐ３或Ｐ５）……(p1 | p2 | p3) ^ (p2 | p3 |p5)……，看結(jié)果值是否為真值。 如果輸入Ｐ有２０個(gè)引腳，就有２^２０種可能，必須一個(gè)一個(gè)布爾函數(shù)去試； 如果輸入Ｐ有３０個(gè)引腳，就必須遍歷２^３０次來(lái)計(jì)算多個(gè)三析取范式是否的結(jié)果值是否為真值，同樣必須一個(gè)一個(gè)布爾函數(shù)去試。 它顯然是組合爆炸的。 在實(shí)際的布爾邏輯與安全的研究中，還明確了排列數(shù)Ｎ！甚至比指數(shù)２^Ｎ的計(jì)算量更大。 證明它是ＮＰ難題很簡(jiǎn)單：給定一個(gè)例子，它是非確定性圖靈機(jī)可驗(yàn)證的。 |
2樓2012-11-11 18:01:33
chentianyu1
木蟲 (小有名氣)
- 應(yīng)助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時(shí)
- 蟲號(hào): 532712
- 注冊(cè): 2008-03-25
- 性別: GG
- 專業(yè): 計(jì)算機(jī)網(wǎng)絡(luò)
3樓2012-11-11 18:34:22
ftai
金蟲 (著名寫手)
- 應(yīng)助: 19 (小學(xué)生)
- 金幣: 7786.4
- 散金: 574
- 紅花: 7
- 帖子: 1412
- 在線: 356.1小時(shí)
- 蟲號(hào): 2101685
- 注冊(cè): 2012-11-02
- 性別: GG
- 專業(yè): 信息安全
4樓2012-11-11 18:50:02
chentianyu1
木蟲 (小有名氣)
- 應(yīng)助: 67 (初中生)
- 金幣: 2579
- 散金: 66
- 帖子: 252
- 在線: 450.2小時(shí)
- 蟲號(hào): 532712
- 注冊(cè): 2008-03-25
- 性別: GG
- 專業(yè): 計(jì)算機(jī)網(wǎng)絡(luò)
5樓2012-11-11 19:56:39
emmett08
金蟲 (正式寫手)
- 應(yīng)助: 17 (小學(xué)生)
- 金幣: 2958.8
- 散金: 2432
- 紅花: 8
- 帖子: 426
- 在線: 368.6小時(shí)
- 蟲號(hào): 1945437
- 注冊(cè): 2012-08-19
- 性別: GG
- 專業(yè): 模式識(shí)別
6樓2012-11-12 20:47:32
zhongyantao
鐵蟲 (著名寫手)
- 應(yīng)助: 3 (幼兒園)
- 金幣: 810.8
- 散金: 80
- 紅花: 3
- 帖子: 1062
- 在線: 275.7小時(shí)
- 蟲號(hào): 2052020
- 注冊(cè): 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ā)表 | |
|---|---|---|---|---|
|
[考研] 333求調(diào)劑 +3 | ALULU4408 2026-03-23 | 3/150 |
|
|---|---|---|---|---|
|
[考研] 考研化學(xué)308分求調(diào)劑 +7 | 你好明天你好 2026-03-23 | 8/400 |
|
|
|
[考研] 一志愿上海交大生物與醫(yī)藥專碩324分，求調(diào)劑 +5 | jiajunX 2026-03-22 | 5/250 |
|
|
|
[考研] 08工學(xué)調(diào)劑 +7 | 用戶573181 2026-03-20 | 11/550 |
|
|
|
[考研] 081700 調(diào)劑 267分 +5 | 迷人的哈哈 2026-03-23 | 5/250 |
|
|
|
[考研] 276求調(diào)劑。有半年電池和半年高分子實(shí)習(xí)經(jīng)歷 +8 | 材料學(xué)257求調(diào)劑 2026-03-23 | 9/450 |
|
|
|
[考研] 0854電子信息求調(diào)劑 +3 | α____ 2026-03-22 | 3/150 |
|
|
|
[考研] 311求調(diào)劑 +6 | 冬十三 2026-03-18 | 6/300 |
|
|
|
[考研] 環(huán)境學(xué)碩288求調(diào)劑 +6 | 皮皮皮123456 2026-03-22 | 6/300 |
|
|
|
[考研] 求調(diào)劑院校信息 +6 | CX 330 2026-03-21 | 6/300 |
|
|
|
[考研] 260求調(diào)劑 +3 | 朱芷琳 2026-03-20 | 4/200 |
|
|
|
[考研] 生物學(xué)調(diào)劑 +5 | Surekei 2026-03-21 | 5/250 |
|
|
|
[考研] 一志愿華中科技大學(xué)071000，求調(diào)劑 +4 | 沿岸有貝殼6 2026-03-21 | 4/200 |
|
|
|
[考研] 一志愿深大，0703化學(xué)，總分302，求調(diào)劑 +4 | 七月-七七 2026-03-21 | 4/200 |
|
|
|
[考研] 302求調(diào)劑 +12 | 呼呼呼。。。。 2026-03-17 | 12/600 |
|
|
|
[考研] 083200學(xué)碩321分一志愿暨南大學(xué)求調(diào)劑 +3 | innocenceF 2026-03-17 | 3/150 |
|
|
|
[考研] 288求調(diào)劑 +16 | 于海海海海 2026-03-19 | 16/800 |
|
|
|
[考研] 290求調(diào)劑 +7 | ^O^乜 2026-03-19 | 7/350 |
|
|
|
[考研] 材料學(xué)求調(diào)劑 +4 | Stella_Yao 2026-03-20 | 4/200 |
|
|
|
[考研] 收復(fù)試調(diào)劑生 +4 | 雨后秋荷 2026-03-18 | 4/200 |
|