为什么SAT在理论计算机科学中如此重要？

解答动态

• 

  SAT是Stephen Cook的开创性中第一个被证明是NP完全的问题。即使是现在，在介绍NP完备性理论时，出发点通常是SAT的NP完备性。
  SAT也适用于非常成功的启发式算法，这些算法由SAT solvers软件实现。因此，将问题有效地表述为SAT的实例是非常有实际意义的。
  SAT也表现为细粒度复杂性，其主要假设之一是强指数时间假设，这是关于SAT.
  
• 

  的计算复杂性的一个猜想值得一提的是，数学家们甚至在SAT被证明是NP完全之前就关心它了。例如，见戈德尔1956年写给冯·诺依曼的信，其中已知SAT为$\Omega（n）$（我认为这仍然是已知的最佳下限，尽管我们至少知道一些下限的显式常数因子），并讨论了如果SAT是$O（n^2）$，它将对数学产生巨大的影响丰满度：
  一罐显然很容易构造一个图灵机，对于一阶谓词逻辑中的每个公式$F$和每个自然数$n$，允许确定是否有长度为$n$（长度=符号数）的$F$证明。设$\Psi（F，n）$为机器需要的步数，设$\phi（n）=\max\u F\Psi（F，n）$。问题是，$\psi（n）$对于一台最佳机器的增长速度有多快。可以证明$\psi（n）≥kn$。如果真的有一台机器有$\phi（n）\sim kn$（甚至$\sim kn^2$），这将产生最重要的后果。也就是说，这显然意味着，尽管Entscheidungsproblem是不可判定的，数学家关于是或否问题的脑力劳动可以完全被机器所代替。
  …
  毕竟$\phi（n）\sim kn$（或$\sim kn^2$）只意味着相对于试错的步数可以从$n减少到$n$到$\log N$（或$（\log N）^2$）。然而，在其它有限问题中，例如在使用互易律的重复应用计算二次剩余符号时，会出现这种强约化。例如，我们想知道一个数的素性的确定情况，以及有限组合问题中的步数相对于简单的穷举搜索可以减少到多大程度。
  [1]这里讨论的问题可能比SAT更接近TQBF，但是Arora巴拉克把它描述成坐在路旁，而我不是逻辑学家
• End