這是52個密碼學知識點的第五篇。我們繼續關于NP的復雜性理論部分。

上周,Ryan給我們介紹了P類復雜問題的定義:

• P 就是一類能被確定的圖靈機在有限時間內判定的語言。
  這周我們介紹另一個復雜類:

• NP就是一類能被非確定的圖靈機在有限時間內判定的語言。

什么是非確定的圖靈機(NDTM)
NDTM就是一種轉換函數有多個返回值的圖靈機。(實際上這不是一個轉換函數，我們可以叫它一個轉換關系)因此NDTM對輸入看起來就像一顆樹。在每個分支節點上都提供了多個可能的值(子節點).NDTM接收這個輸入當且僅當樹中至少有一個分支的輸入處于接收狀態。這個定義從語言關系到決策到計算問題的方法和上周定義P的時候一樣。

一些NP問題的例子
我們以一個簡單的例子開始:路徑查找。給一個有向圖(n個節點) 是否有從點A到點B的路徑。我們怎么在NP類中得到答案?好的，存在一個NDTM能解決它，十分簡單，只要嘗試所有的路線，只要有一個分支那么就有一個交叉點，如果一個分支到達了B那么該分支將終止于accept狀態。任意一條分支在遍歷n步之后自動結束并處于拒絕狀態。(因為任何路徑最多包含n-1條邊，所以將檢測到任何有效的路徑，因此這臺機器將正確的決定是否存在這樣的一個路徑)。

一個NP問題的重要的例子就是可滿足行問題:

• SAT問題:給n個變量一個表達式(與或非表達式)，是否有一個變量的賦值能使得表達式為True?

例如，在表達式(A∨B)∧(A∨?B)是可滿足的。因為有一個合法的賦值A=B=True。注意:在標準形式中，這是個決定性問題，即我們只需要知道存不存在，不需要找到。

所以有很多NP問題.NP問題的價值在哪
首先，我們知道P?NP 因為DTM是一種NDTM(顯而易見)。因此實際上我們的問題就是我們能不能找到一件我們能用NP做的問題但是我們沒辦法用P完成?這就是P=？NP問題，這是一個開放問題。當然我們也發現了NP中已知但是P中未知的問題，也許在未來的研究中這些問題能被P解決。

很多有趣的密碼系統(特別是在公鑰中)都是基于計算問題是"困難"的假設而是安全的，這意味著至少與NP中的任何問題一樣困難。也就是說，很多方案都是基于我們認為難的問題，如果你能創建一個算法來解決這些問題，你也可以用這個算法解決其他當前認為是難的問題。

Cook-Levin定理提供了一個有趣的證明思路。沒有NP問題是比SAT難的(已經有證明了SAT是最難的NP問題(，即NP完全問題)。這就是說如果我們有一個oracle(就是一個問詢，一個有輸入輸出的算法)能解決SAT問題，通過問這個oracle幾個被構造的問題，也可以解決任何其它NP問題。這讓SAT成為了第一個NP完全問題的例子。因此為了證明問題X至少和解決NP問題一樣難(NP難問題)，如果我們能解決X問題，那么我們就能解決SAT問題。

原文地址：http://bristolcrypto.blogspot.com/2014/11/52-things-number-5-what-is-meant-by.html
轉載地址：https://www.cnblogs.com/zhuowangy2k/p/11518651.html

總結

以上是生活随笔為你收集整理的[密码学基础][每个信息安全博士生应该知道的52件事][Bristol Cryptography][第5篇]复杂性类NP是什么意思?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。