首先，我們限制函數只能輸出 0 和 1，并稱這樣的函數為問題。因為您可以單獨查詢較長結果的每個位，所以這不是一個真正的限制，但它可以使理論更容易。現在我們要測量解決給定問題（計算函數）的“復雜程度”。對于數學函數f的特定機器實現M，我們總是可以計算在特定輸入x上計算f所需的步數 - 這稱為x在M上的運行時間。究竟什么是“步驟”，在這種情況下并不太重要。由于程序對于更大的輸入旺旺需要更多的步數，而運行時間以輸入的大小或長度（位數）來衡量的。這就是例如”n2 算法”的來源 -- 這就是一個當輸入值大小為 n 時，至多需要n2 個步數的算法。這里的”程序”和”算法”廣義上是相同的。
對于某些k，其運行時間最多為n k的程序也稱為“多項式時間程序”。
復雜性理論中的兩個主要問題類型是P和NP：
P是具有多項式時間程序的一類問題類 雖然 k 的指數對于一些問題來說確實非常大，但是實際上對于那些非人造的，k 不大于 4 的 P 問題仍然被認為是可以“解決的”的問題。要確認一筆
比特幣的交易就是一個 P 問題，因為經過評估它需要一個多項式時間（并且只能輸出 0 和 1）。簡單的說就是，如果你只是計算一些值而不去“搜索”，那么這個問題就是 P 問題。但是如果你不得不搜索一些東西，那么你就會進入到另一個叫做 NP 問題的類別中。
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
