摘要訊息 : 如何判斷一個問題是否可解, 複雜性多高, 複雜度如何以及放在什麼樣的計算模型上解決?
0. 前言
首先要向大家介紹什麼是計算理論. 這是一個電腦科學的分支, 而且是完完全全理論性的一個研究分支. 我們都知道, 不管是硬體還是軟體, 它都是存在大量實際運用的, 但是這個分支是硬體理論和軟體理論的結合, 而且包含了大量數學. 我們在分析演算法的時候, 通常告訴大家要解決某一個問題的演算法的時間複雜度和空間複雜度. 然而在這個系列的文章中, 我要告訴大家, 對於一個問題 :
請注意區分複雜性和複雜度這兩個概念, 複雜性是指一個問題難不難, 而複雜度是用於描述解決一個問題需要多少空間和時間.
更新紀錄 :
- 2022 年 5 月 26 日進行第一次更新和修正.
1. 計算複雜性理論
Tip : 為了方便大家理解, 我們並不首先介紹計算模型.
我們遇到的問題是多種多樣的. 從我們人的直覺上, 我們其實可以感覺某些問題是容易解決的, 某些問題是難以解決的. 當然, 這裡有一個前提, 就是這個問題可以被解決. 用你的直覺去感受, 排序是否困難呢? 很顯然, 這不難. 現在換一個問題. 對於大學某個學院, 有若干個老師, 若干個班, 這些老師要教授學生多個不同的課程, 如何編排這些課程使得
- 同一老師不在同一時間內教授不同的班;
- 同一老師不在同一時間內教授不同的課程;
- 同一班學生不在同一時間上不同的課;
- 一個課室不在同一時間供兩個班上課;
- ...
上面列出的, 都是編排課程中不能出現的衝突. 用你的直覺去感受, 這個問題是否困難呢? 我覺得至少是難的, 因為我有必要列舉出所有的可能性, 然後排除掉衝突的部分. 當然, 也可以運氣很好, 用直覺隨機排課的第一次就遇到了正確答案. 如果老師班機和課程的數量變得很多, 那麼直覺還能夠採用嗎?
再舉一個實例, 從地圖中某幾個地點, 找到起始位置到終點最短的走法. 這個問題也不是特別難. 但是如果要求所有地點都只能走一次, 最後還要回到起始位置, 並且走的路徑最短, 這個問題是不是就難很多?
其實人確實是可以從直觀上去感覺一個問題是否是難的, 但是直覺不總是不準確的. 那麼是什麼使得某些問題很難計算, 又是什麼使得某些問題很容易計算呢? 這個問題, 至今沒有答案. 但是, 我們確實可以根據一個問題的計算難度, 給問題劃分類別. 從這個角度來說, 我們雖然不能證明某些問題是難計算的, 但是可以以此為基準, 我們至少有一些證據和理論來表明某一個問題至少和另外一個問題一樣難. 這便是計算複雜性理論的本質.
那麼這個研究分支的意義在哪裡呢? 面對一個很難計算且實體特徵很大的問題, 超級電腦都很難很短時間內給出答案, 我們會轉換這個問題, 試著能否通過化約為其它問題, 使得問題變得容易解決. 如果不行的情況下, 我們會採用另一個原則, 就是獲得一個並不是特別完美的解. 例如可以獲得正確解, 但是有一定機率出錯, 這個出錯的機率我們可以接受; 或者得到的解不精確, 但是接近正確解. 再者, 如果某一個問題僅僅在某些情況下是困難的, 但是絕大多數情況下是容易的. 那麼一個偶爾運作稍慢的程式, 也可以令人接受.
2. 可計算理論
當現代面對一個需要巨量計算問題的時候, 我們首先想到使用電腦進行計算. 而某一些問題是不能用電腦解決的, 比如尋找 \frac {sinx}{x} 的原函數初等表達, 即 \displaystyle {\int \frac {sinx}{x}dx}. 通過電腦計算函數的原函數似乎很自然, 但是某一些函數的原函數是任何電腦都無法完成的 (準確地來說, 這裡的電腦是指決定性杜林機, 《貪婪演算法》第 2 節), 因為它們就不存在初等表達. 類似地, 某些問題是無解的, 自然也就不能使用電腦來解決. 計算複雜性理論將問題評判問題的難解性, 而可計算理論評判問題的可解性.
3. 自動機理論
自動機理論闡述了計算的數學模型是如何定義的以及有什麼樣的性質. 這些模型在電腦科學中有著若干應用, 例如有限狀態機和上下文無關文法. 自動機理論是可計算理論和計算複雜性理論的基礎, 它們都需要精確的自動機理論定義. 另外, 自動機理論還可以幫助我們提升形式化語言的能力.
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :
