為什么SAT在理論計算機科學中如此重要？

解答動態(tài)

• 

  SAT是Stephen Cook的開創(chuàng)性中第一個被證明是NP完全的問題。即使是現(xiàn)在，在介紹NP完備性理論時，出發(fā)點通常是SAT的NP完備性。
  SAT也適用于非常成功的啟發(fā)式算法，這些算法由SAT solvers軟件實現(xiàn)。因此，將問題有效地表述為SAT的實例是非常有實際意義的。
  SAT也表現(xiàn)為細粒度復雜性，其主要假設之一是強指數(shù)時間假設，這是關(guān)于SAT.
  
• 

  的計算復雜性的一個猜想值得一提的是，數(shù)學家們甚至在SAT被證明是NP完全之前就關(guān)心它了。例如，見戈德爾1956年寫給馮·諾依曼的信，其中已知SAT為$\Omega（n）$（我認為這仍然是已知的最佳下限，盡管我們至少知道一些下限的顯式常數(shù)因子），并討論了如果SAT是$O（n^2）$，它將對數(shù)學產(chǎn)生巨大的影響豐滿度：
  一罐顯然很容易構(gòu)造一個圖靈機，對于一階謂詞邏輯中的每個公式$F$和每個自然數(shù)$n$，允許確定是否有長度為$n$（長度=符號數(shù)）的$F$證明。設$\Psi（F，n）$為機器需要的步數(shù)，設$\phi（n）=\max\u F\Psi（F，n）$。問題是，$\psi（n）$對于一臺最佳機器的增長速度有多快。可以證明$\psi（n）≥kn$。如果真的有一臺機器有$\phi（n）\sim kn$（甚至$\sim kn^2$），這將產(chǎn)生最重要的后果。也就是說，這顯然意味著，盡管Entscheidungsproblem是不可判定的，數(shù)學家關(guān)于是或否問題的腦力勞動可以完全被機器所代替。
  …
  畢竟$\phi（n）\sim kn$（或$\sim kn^2$）只意味著相對于試錯的步數(shù)可以從$n減少到$n$到$\log N$（或$（\log N）^2$）。然而，在其它有限問題中，例如在使用互易律的重復應用計算二次剩余符號時，會出現(xiàn)這種強約化。例如，我們想知道一個數(shù)的素性的確定情況，以及有限組合問題中的步數(shù)相對于簡單的窮舉搜索可以減少到多大程度。
  [1]這里討論的問題可能比SAT更接近TQBF，但是Arora巴拉克把它描述成坐在路旁，而我不是邏輯學家
• End