文章目錄

• 一、NP 類不同表述
• 二、團(tuán)問(wèn)題
• 三、P 對(duì) NP 問(wèn)題 ( P vs NP )

一、NP 類不同表述

---

$\mathrm{N}\mathrm{P}$ 對(duì)應(yīng)的 確定性圖靈機(jī) 表述 :

$\mathrm{N}\mathrm{P}$ 類就是有 多項(xiàng)式時(shí)間驗(yàn)證機(jī) 的 語(yǔ)言 ( 計(jì)算問(wèn)題 ) 的總體集合 ;

其中的 多項(xiàng)式時(shí)間驗(yàn)證機(jī) 是一個(gè) 確定性圖靈機(jī) , 驗(yàn)證機(jī) ;

$\mathrm{N}\mathrm{P}$ 對(duì)應(yīng)的 非確定性圖靈機(jī) 表述 :

$\mathrm{N}\mathrm{P}$ 概念轉(zhuǎn)化到 非確定性圖靈機(jī) 中 , 有另外一個(gè)等價(jià)定義 ;

如果一個(gè)語(yǔ)言屬于 $\mathrm{N}\mathrm{P}$ , 指的是有一些 非確定性圖靈機(jī) 可以在 多項(xiàng)式時(shí)間 內(nèi)解決該問(wèn)題 ;

上述兩個(gè)定義時(shí)等價(jià)的 ;

確定性圖靈機(jī) 多項(xiàng)式時(shí)間 內(nèi) 驗(yàn)證 ,

等價(jià)于 ,

非確定性圖靈機(jī) 多項(xiàng)式時(shí)間 內(nèi) 解決 ;

二、團(tuán)問(wèn)題

---

現(xiàn)在討論哪些計(jì)算問(wèn)題在 $\mathrm{N}\mathrm{P}$ 中 ;

團(tuán)問(wèn)題 是一個(gè)經(jīng)典的 $\mathrm{N}\mathrm{P}$ 問(wèn)題 ;

團(tuán) 是一個(gè)無(wú)向圖 點(diǎn)集 的 子集 , 使得 該點(diǎn)集子集 中 任何兩個(gè)節(jié)點(diǎn)之間都有邊相連 ;

團(tuán)問(wèn)題 就是 判定無(wú)向圖中 , 是否包含有 $\mathrm{k}$ 個(gè)節(jié)點(diǎn)的 團(tuán) ;

上述團(tuán)問(wèn)題 , 是 $\mathrm{N}\mathrm{P}$ 問(wèn)題 ;

給定一個(gè)無(wú)向圖 , 其中有一個(gè) $\mathrm{n}$ 個(gè)節(jié)點(diǎn)組成的集合 , 驗(yàn)證該 $\mathrm{n}$ 集合是否是團(tuán) ;

驗(yàn)證的方法就是看這 $\mathrm{n}$ 元集中的節(jié)點(diǎn)之間兩兩之間是否有邊相連即可 ;

驗(yàn)證所花的時(shí)間是多項(xiàng)式時(shí)間 , 該計(jì)算問(wèn)題在 $\mathrm{N}\mathrm{P}$ 中 ;

三、P 對(duì) NP 問(wèn)題 ( P vs NP )

---

$\mathrm{P}$ 對(duì) $\mathrm{N}\mathrm{P}$ 問(wèn)題 是計(jì)算機(jī)科學(xué)中最著名的問(wèn)題 ;

該問(wèn)題直接涉及到對(duì)計(jì)算實(shí)質(zhì)的理解 , 與密碼學(xué)密切相關(guān) ;

目前沒(méi)有實(shí)質(zhì)性進(jìn)展 ;

參考 : 百度百科 - P 對(duì) NP 問(wèn)題

$\mathrm{P}?\mathrm{N}\mathrm{P}?\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}={?}_{\mathrm{k}}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{{\mathrm{n}}^{\mathrm{k}}})$

$\mathrm{P}$ 是 $\mathrm{N}\mathrm{P}$ 的子集 ,

$\mathrm{N}\mathrm{P}$ 是 指數(shù)級(jí) ( $\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{t}$ ) 時(shí)間 ( $\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}$ ) 的子集 ,

非確定性圖靈機(jī) , 如果要使用 確定性圖靈機(jī) 來(lái)模仿的話 , 時(shí)間復(fù)雜度時(shí)指數(shù)級(jí)的 ;

參考博客 【計(jì)算理論】計(jì)算復(fù)雜性 ( 證明 非確定性圖靈機(jī) 與 確定性圖靈機(jī) 的時(shí)間復(fù)雜度 之間的指數(shù)關(guān)系 )

上述 $3$ 個(gè)不同的復(fù)雜類 , 對(duì)應(yīng)的計(jì)算模型是不一致的 ,

$\mathrm{P}$ 對(duì)應(yīng)的是 確定性單個(gè)帶子圖靈機(jī) ,

$\mathrm{N}\mathrm{P}$ 對(duì)應(yīng)的是 非確定性的單個(gè)帶子圖靈機(jī) ,

$\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}$ 對(duì)應(yīng)的是 非確定性的單個(gè)帶子圖靈機(jī) ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( NP 类不同表述 | 团问题 | P 对 NP 问题 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。