可計算性和複雜性/複雜性
< 可計算性和複雜性
複雜性理論是理論計算機科學的核心領域，對整個計算機科學產生了重大影響。複雜性理論試圖找出執行特定任務或解決特定問題需要多少資源（時間、空間、能量等）。它試圖將問題分類到複雜性類別中，以便同一類別中的問題對解決它們所需的資源具有類似的要求。例如，屬於複雜性類別的所有問題，根據定義，都有一種演算法可以相對快地解決它們，即在多項式時間內解決它們。
當我們談論解決一個特定問題時，我們可能想到判定給定輸入圖是否連通的問題。這個問題可以以數學方式形式化為集合，即所有連通圖的集合。我們說一個演算法解決問題，如果它返回是，如果輸入是的成員，返回否，如果不是。在我們的例子中，解決的演算法將讀取某個輸入圖，計算某些內容，然後如果它發現輸入圖是連通的，就說是。這個框架的妙處在於，集合就是我們要分析的問題。
給定一個問題，自然的問題是
- 解決的最快的演算法有多快？
- 解決的最佳演算法需要多少空間（例如硬碟）？
- 如果我的空間不多（例如，在古老的手機上），我還能找到的演算法嗎？然後我仍然擁有最快的演算法嗎？
- 假設你有一個非常困難的問題，你就是想不出如何有效地解決它？你能證明它不能被有效地解決嗎？
此頁面尚未開發。