文章目錄

• 一、P 類
• 二、有效算法函數(shù)
• 三、NP 直覺
• 四、NP 簡介
• 五、NP 嚴(yán)格數(shù)學(xué)定義

一、P 類

---

時間復(fù)雜度類 :

定義 時間復(fù)雜度類 $\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(\mathrm{t}(\mathrm{n}))$ , $\mathrm{L}$ 是一個語言 , 對應(yīng)一個計算問題 , 如果可以被 單個帶子的圖靈機 $\mathrm{T}\mathrm{M}$ 進(jìn)行判定的話 , 它的 時間復(fù)雜度是 $\mathrm{O}(\mathrm{t}(\mathrm{n}))$ ;

符號化表示 : $\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(\mathrm{t}(\mathrm{n}))=\{\mathrm{L}:\mathrm{L}是一個語言,該語言可以被時間復(fù)雜度\mathrm{O}(\mathrm{t}(\mathrm{n}))的單個帶子圖靈機識別\}$

$\mathrm{P}$ 類 :

所有 能夠被 確定性 單個帶子圖靈機 , 在 多項式時間 內(nèi) , 能夠被 判定的計算問題 ,

將這些問題放在一起 ( 廣義并集 $?$ ) , 組成一個整體 , 就稱為 $\mathrm{P}$

符號化表示 : $\mathrm{P}={?}_{\mathrm{k}}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}({\mathrm{n}}^{\mathrm{k}})$

$\mathrm{P}$ 類 , 就是定義 有效算法 所組成的類 ,

有效算法 , 就是在 多項式時間 內(nèi) , 可以執(zhí)行完畢 , 得到一個確定的結(jié)果的算法 ;

確定的結(jié)果就是 接受狀態(tài) , 或 拒絕狀態(tài) ;

二、有效算法函數(shù)

---

上述 $\mathrm{P}$ 類 是對 有效算法 進(jìn)行了嚴(yán)格的數(shù)學(xué)定義 ;

計算理論的意義就是 證明 有哪些計算問題 , 是不存在有效算法的 , 如果沒有確定性的有效算法 , 就需要 找近似的算法 , 解決同樣的問題 , 而不是確定性的算法 ;

有效算法是一個函數(shù) , 該函數(shù)的主要依賴于 輸入字符串大小 ;

如果給定一個確定性圖靈機 , 定義其時間復(fù)雜度 , 通過 $\mathrm{f}$ 函數(shù)進(jìn)行定義 , $\mathrm{f}$ 函數(shù)是從 自然數(shù)集 $\mathrm{N}$ 到 自然數(shù)集 $\mathrm{N}$ 的映射 ,

符號化表示 : $\mathrm{f}:\mathrm{N}\to \mathrm{N}$ ,

定義域中的自然數(shù) $\mathrm{N}$ 指的是 輸入字符串大小 ,

值域中的自然數(shù) $\mathrm{N}$ 指的是 圖靈機計算所執(zhí)行的步數(shù) ;

時間復(fù)雜度 $\mathrm{f}(\mathrm{n})$ 定義方式 : 將所有長度為 $\mathrm{n}$ 的字符串 , 依次輸入到圖靈機中進(jìn)行計算 , 所有的計算中取最大的計算步數(shù) , 作為 $\mathrm{f}(\mathrm{n})$ 的取值 ;

三、NP 直覺

---

有兩個問題 ,

問題 $\mathrm{A}$ , 花了一天時間 , 找到了解決方案 ,

問題 $\mathrm{B}$ , 已經(jīng)存在了解決方案 , 讀懂該方案 , 花了一天時間 ,

這兩個問題 , 在第一印象直覺中 , 問題 $\mathrm{B}$ 更難一些 ;

理解 問題 $\mathrm{B}$ 的解決方案 , 是一個簡單的任務(wù) ,

解決 問題 $\mathrm{A}$ , 是更難的任務(wù) ,

兩者都花了一天的時間 , 直覺上感覺問題 $\mathrm{B}$ 更難 ;

解決問題 , 一般比 理解解決問題的方案 , 更難一些 ;

類似于 學(xué)習(xí) 和 科研 的難度 ,

學(xué)習(xí) 是理解現(xiàn)有解決方案 , 是簡單任務(wù) ,

科研 是提出解決方案 , 是比較難的任務(wù) ;

通常情況下 , 一個問題 , 沒有答案 , 要找到答案的話 , 需要創(chuàng)造性 ,

如果已經(jīng)有一個答案 , 驗證這個答案的正確性 , 通常 不需要創(chuàng)造性的 , 只需要有理解能力就足夠了 ;

四、NP 簡介

---

$\mathrm{P}$ 目的是確定哪些 計算問題 是 可以被 有效解決 的計算問題 ;

$\mathrm{N}\mathrm{P}$ 目的是確定哪些 計算問題 是 可以被 有效驗證 的計算問題 ;

驗證 : 驗證值的是 , 計算問題 已經(jīng)有正確的答案 , 將正確的答案 , 根據(jù)某些有限的指令 , 規(guī)則 , 驗證 算法的 每一步是否正確 ;

驗證 相當(dāng)于 學(xué)習(xí)的過程 , 解決 相當(dāng)于 科研過程 ;

$\mathrm{N}\mathrm{P}$ 對應(yīng)的計算問題 , 指的是能夠 在 多項式時間內(nèi) , 能夠 驗證 的計算問題 ;

$\mathrm{P}$ 對應(yīng)的計算問題 , 指的是能夠 在 多項式時間內(nèi) , 能夠 解決 的計算問題 ;

$\mathrm{P}$ 是包含在 $\mathrm{N}\mathrm{P}$ 中的 : 如果有計算問題 , 在 多項式時間 內(nèi)能夠 解決 , 肯定就能在 多項式時間內(nèi) 能夠 驗證 ;

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

五、NP 嚴(yán)格數(shù)學(xué)定義

---

$\mathrm{N}\mathrm{P}$ 是 多項式時間 內(nèi)的 驗證機 ;

驗證機 : $\mathrm{A}$ 語言 ( 計算問題 ) 的 驗證機 $\mathrm{V}$ ;

$<\mathrm{w},\mathrm{c}>$ 含義 : 給定一個 輸入 $\mathrm{w}$ , $\mathrm{w}$ 是輸入字符串 , $\mathrm{c}$ 是輸入 $\mathrm{w}$ 被接受的情況下的輸入 , 即正確的輸入 ;

$\mathrm{A}$ 語言 ( 計算問題 ) 的 驗證機 $\mathrm{V}$ 條件 : 給定了正確的輸入 $\mathrm{c}$ , 讓驗證機 $\mathrm{V}$ 進(jìn)行一步步驗證 , 如果 驗證機 $\mathrm{V}$ 接受了輸入的字符串 $\mathrm{c}$ , 稱 驗證機 $\mathrm{V}$ 就是計算問題 $\mathrm{A}$ 的驗證機 ;

符號化表示 : $\mathrm{A}=\{\mathrm{w}:驗證機\mathrm{V}接受<\mathrm{w},\mathrm{c}>中正確的輸入\mathrm{c}\}$

驗證操作 : 已經(jīng)有了正確答案 $\mathrm{c}$ , 有一個有限的規(guī)則 , 將正確答案 $\mathrm{c}$ 每一步 , 代入有限規(guī)則中進(jìn)行驗證是否正確 ;

驗證時間 : 已經(jīng)有了正確答案 $\mathrm{c}$ , 有一個有限的規(guī)則 , 將正確答案 $\mathrm{c}$ 每一步 , 代入有限規(guī)則中進(jìn)行驗證是否正確 , 最后記錄整個驗證過程所花費的時間 ; 即 學(xué)習(xí)的過程 ;

$\mathrm{N}\mathrm{P}$ 計算問題要求 : 如果花費的時間 在 多項式時間 之內(nèi) , 就稱 該問題是 $\mathrm{N}\mathrm{P}$ 對應(yīng)的計算問題 ;

多項式時間驗證機 : $\mathrm{A}$ 語言 如果 可以在 多項式時間 內(nèi) 可以 驗證 的話 , 就稱該語言 有一個 多項式時間驗證機 ;

$\mathrm{N}\mathrm{P}$ 類就是有 多項式時間驗證機 的 語言 ( 計算問題 ) 的總體集合 ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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