這個……有反面教材的意義吧……
首先，姜教授之前做了什麼工作我不清楚，但是就這件事來看，實在看不出來是接受過計算機高等教育的人。
我是在法國學的理論計算機。在第一個學期的課（相當於大三）裡，有一門《語言和計算複雜度》的課，然後到了碩士，每個學期都有關於計算複雜度的課程，而且是逐漸深化的。這可見計算複雜度在計算機研究中的重要性。
為什麼？因為除了知道一件事能不能用計算機去做以外，要做這件事需要多少資源也是很重要的。都要花時間，用兩秒算完和用兩年算完，在現實中的意義就完全不一樣；都要花儲存空間，需要1MB和需要1PB，差距更加巨大。所以，計算機的演算法通常都不是說只要能算出來就可以了，而是要具體考證這些演算法要花上多少時間和空間。
現在，我們來分析一下姜教授的演算法到底是怎麼回事。雖然姜教授本人言之鑿鑿，說很多人都看不懂這個演算法的精妙之處，但恕我直言，這看起來更像是本科生腦洞大開之後的胡言亂語，而不是經過仔細思考的研究結果。
演算法很簡單：對於k-SAT，維護一個列表，每一格對應給所有變數賦值的每一種可能性，然後考慮每一個析取子句，將不可能滿足這個子句的賦值可能性全部劃掉，然後看看有沒有剩下的可能性。
演算法是對的，不對就見鬼了。但是，執行這個演算法，需要多少時間？
假設我們有n個變數，c個子句。考慮每一個子句時，因為每個子句都包含k個變數，所以不滿足這個子句的賦值可能性，對於這k個變數來說只有一種，但對於所有變數來說就有2^(n-k)種，因為除此之外的變數可以任取。要劃掉所有這些可能性，就需要2^(n-k)次操作，c個子句和起來就是c*2^(n-k)次。都不需要考慮前前後後的操作，就中間的這一步，顯然就需要指數時間。指數時間就不是多項式時間，即使演算法本身正確，但花的時間實在太長了。
更糟糕的是，這個演算法需要的空間同樣是指數的，這個問題甚至比指數時間更嚴重，因為在實踐上和在複雜度理論上，空間比時間要金貴。姜教授的演算法，即使集合地球上所有的現有儲存資源，也只能解決不超過30個變數的問題。而目前最先進的SAT Solver，可以在個人計算機上解決變數上千的問題。當然，理論最優不代表實踐最優，但姜教授的演算法在這個問題上還是差了一些。
就這樣的“多項式演算法”，在我原來的學校隨便抓一個剛入學上了兩天課的學生，都能輕鬆指出其中的問題。如果姜教授敢於發表這樣的東西，那我只能讚歎他過人的勇氣。
另外，據我所知，姜教授現在好像還有另一個據稱能解決另一個NPC問題的演算法，還說論文已經投稿到國際知名雜誌上了。結果不知道出來了沒有，但我想，如果姜教授現在還沒有認識到這個SAT演算法的問題的話，那麼論文的命運也就一目瞭然了。
這個……有反面教材的意義吧……
首先，姜教授之前做了什麼工作我不清楚，但是就這件事來看，實在看不出來是接受過計算機高等教育的人。
我是在法國學的理論計算機。在第一個學期的課（相當於大三）裡，有一門《語言和計算複雜度》的課，然後到了碩士，每個學期都有關於計算複雜度的課程，而且是逐漸深化的。這可見計算複雜度在計算機研究中的重要性。
為什麼？因為除了知道一件事能不能用計算機去做以外，要做這件事需要多少資源也是很重要的。都要花時間，用兩秒算完和用兩年算完，在現實中的意義就完全不一樣；都要花儲存空間，需要1MB和需要1PB，差距更加巨大。所以，計算機的演算法通常都不是說只要能算出來就可以了，而是要具體考證這些演算法要花上多少時間和空間。
現在，我們來分析一下姜教授的演算法到底是怎麼回事。雖然姜教授本人言之鑿鑿，說很多人都看不懂這個演算法的精妙之處，但恕我直言，這看起來更像是本科生腦洞大開之後的胡言亂語，而不是經過仔細思考的研究結果。
演算法很簡單：對於k-SAT，維護一個列表，每一格對應給所有變數賦值的每一種可能性，然後考慮每一個析取子句，將不可能滿足這個子句的賦值可能性全部劃掉，然後看看有沒有剩下的可能性。
演算法是對的，不對就見鬼了。但是，執行這個演算法，需要多少時間？
假設我們有n個變數，c個子句。考慮每一個子句時，因為每個子句都包含k個變數，所以不滿足這個子句的賦值可能性，對於這k個變數來說只有一種，但對於所有變數來說就有2^(n-k)種，因為除此之外的變數可以任取。要劃掉所有這些可能性，就需要2^(n-k)次操作，c個子句和起來就是c*2^(n-k)次。都不需要考慮前前後後的操作，就中間的這一步，顯然就需要指數時間。指數時間就不是多項式時間，即使演算法本身正確，但花的時間實在太長了。
更糟糕的是，這個演算法需要的空間同樣是指數的，這個問題甚至比指數時間更嚴重，因為在實踐上和在複雜度理論上，空間比時間要金貴。姜教授的演算法，即使集合地球上所有的現有儲存資源，也只能解決不超過30個變數的問題。而目前最先進的SAT Solver，可以在個人計算機上解決變數上千的問題。當然，理論最優不代表實踐最優，但姜教授的演算法在這個問題上還是差了一些。
就這樣的“多項式演算法”，在我原來的學校隨便抓一個剛入學上了兩天課的學生，都能輕鬆指出其中的問題。如果姜教授敢於發表這樣的東西，那我只能讚歎他過人的勇氣。
另外，據我所知，姜教授現在好像還有另一個據稱能解決另一個NPC問題的演算法，還說論文已經投稿到國際知名雜誌上了。結果不知道出來了沒有，但我想，如果姜教授現在還沒有認識到這個SAT演算法的問題的話，那麼論文的命運也就一目瞭然了。