难解性与 NP 完全问题

Turing Machines

之前我们已经接触过一个简单的计算模型(A simple model of computation): DFAs. 但 DFAs 难以执行除 pattern matching 外的计算任务。我们不禁要问:Is there a more powerful model of computation?

答案是肯定的:大名鼎鼎的 Turing machines 是一种 simple and universal model of computation. 构成其的基本单元仅仅是一个无限长的纸带(tape)与读写头(tape head)。

Tape.

  • Store input, output, and intermediate results.
  • One arbitrarily long strip, divide into cells.
  • Finite alphabet of symbols.

Tape head.

  • Points to one cell of tape.
  • Reads a symbol from active cell.
  • Writes a symbol to active cell (according to the table).
  • Moves one cell at a time.

[1936] Church-Turing thesis. Turing machines can compute any function that can be computed by a physically harnessable process of the natural world.

注意,我们在这里采用的名词是 thesis(论题),而不是严谨的 mathematical theorem(定理)。这是因为 Church-Turing thesis is a statement about the physical world and not subject to proof.

虽然难以被(数学意义上的)证明,论题是可以被证伪(falsified)的。然而自从 Church-Turing thesis 被提出以来还没有任何 counterexamples 被发现。

并且许多已被发现的 models of computation turned out to be equivalent,这可以作为 Turing machines universal 性质的佐证。(注:We use simulation to prove models equivalent)

Church-Turing thesis 有什么意义呢?它揭示了图灵机已经是一个通用的计算模型,因此我们:

  • No need to seek more powerful machines or languages.
  • Enables rigorous study of computation (in this universe).

Intractability

Church-Turing thesis 解决了我们对是否存在 general-purpose computer 的疑问;在此基础之上,计算机科学家们开始探寻 the limits on the power of digital computers.

对于某个问题,我们如何判断它是否能被计算机“高效地”解决?什么样的算法能被视为“高效的”?

  • Measure running time as a function of input size NN.
  • Useful in practice ("efficient") = polynomial time (aNbaN^b) for all inputs.

In practice,只有常数 a,ba,b 都比较小的 poly-time 算法(如 3N23N^2)才能应用到规模较大的问题上。常见的非 poly-time running time 有:

  • Factorial running time: N!=N(N−1)..×2×1N!=N(N-1)..\times2\times1.
  • Exponential growth: abNab^N. Exponential growth dwarfs technological change.

Bird's-eye view. A problem is intractable if it can't be solved in polynomial time.

我们的 desiderata: Prove that a problem is intractable;然而这样的证明通常十分困难:very few successes have been made. 现有的 two problems that probably require exponential time.

  • Given a constant-size problem, does it halt in at most KK (input size = c+lg⁡Kc+\lg{K}) steps?
  • Given NN-by-NN checkers board position, can the first player force (forced capture rule) a win?

Search Problems

LSOLVE (Linear Solve), LP (Linear Programming), ILP (Integer Linear Programming), SAT(Boolean Satisfiability Problem)常常被称为四大基本问题(four fundamental problems),这是因为许多计算问题都能归约到这四个问题上。因此,研究这四个问题有助于我们证明某个其他问题的 intractability 性质。

  • LSOLVE. Given a system of linear equations, find a solution.
  • LP. Given a system of linear inequalities, find a solution.
  • ILP. Given a system of linear inequalities, find a 0-1 solution.
  • SAT. Given a system of boolean equations, find a binary solution.

其中 LSOLVE(Gaussian elimination ∼N3\sim N^3)与 LP(Ellipsoid algorithm)均存在 poly-time algorithms,而对于 ILP 与 SAT,No poly-time algorithm known or believed to exist. 因此我们可以(暂时)认为 ILP 与 SAT 问题是 intractable 的。

这四大基本问题均属于 search problem:该类问题的重要特征之一是我们能很容易地判断某个解的正确性。以四大问题的某个解 SS 为例,我们只需要 plug in values and verify each equation。

Search problem. Given an instance II of a problem, find a solution SS.

Requirement. Must be able to efficiently verify that SS is a solution.

关于 search problem 的定义,可以看看这个帖子下的讨论。说到底这个定义并不是非常严谨,但大多数情况下我们都可以通过 common sense 来进行判断。

我们如何利用这四大基本问题来证明其他问题的 intractability?答案是通过 reduction。在目前的计算理论体系中,SAT 问题可以说是许多 intractable 问题的源头 [stay tuned for NP-completeness]。

目前来讲,对于 SAT 的一个 general instance with nn variables,除了使用 ∼2n\sim 2^n 的 exhaustive search 算法之外没有其他效率更高的算法。No poly-time algorithm for SAT(即,SAT is intractable)已经成为了一个得到共识的 conjecture。

基于这个 conjecture,我们可以得出这样一个结论:If SAT poly-time reduces to YY, then we conclude that YY is (probably) intractable.(注意,这里是 poly-time reduction 而非 linear-time reduction)

Problem XX poly-time reduces [Cook reduction] to problem YY if XX can be solved with:

  • Polynomial number of standard computational steps.
  • Polynomial number of calls to YY.

Karp's problems: more poly-time reductions from SAT

P v.s. NP

  • NP is the class of all search problems.
  • P is the class of search problems solvable in poly-time.

从实践意义的角度来定义,P 与 NP 分别是:

  • NP. What scientists and engineers aspire to compute feasibly.
  • P. What scientists and engineers do compute feasibly.

从定义上来看,P 是 NP 的一个子集;四大问题显然均属于 NP,但只有 LSOLVE 与 LP 问题属于 P。NP 的 N 来自于 Nondeterministic: 之前我们在介绍 NFA 的时候已经简单了解过。Turing machine 同样也分为:

  • Determinisitc: state, input determines next state.
  • Nondeterministic: more than one possible next state.

对于 nondeterministic machine, it can guess the desire solution. 据此我们引入 P 与 NP 的另一个定义:

  • P. Search problems both solvable and verifiable on a deterministic TM.
  • NP. Search problems solvable in poly-time on a nondeterministic TM and verifiable in poly-time on a deterministic TM.

非确定性图灵机(nondeterministic TM, NTM)是一个理论模型,在 natural world 中(至少到目前为止)是无法实现的。我们可以将其理解为一种算法:It at every step tries all possible steps and chooses the best possible next step, therefore guessing the desired solution.

NTM 这一概念存在的意义就是判断某个问题 XX 是否属于 NP 问题:若我们能设计出一个能在 poly-time 内解决 XX 的 NTM,那么 XX 就属于 NP 问题。本质上来讲,verifying a solution in polynomial time with a TM is equivalent to solving in polynomial time with NTM. 这个帖子中的讨论值得参考。

Extended Church-Turing thesis. P = search problems solvable in poly-time in the natural world.

  • Supporting evidence. True for all physical computers.
  • Implication. Suffices to focus on improving implementation of existing designs to make future computers more efficient.

Extended Church-Turing thesis 使我们的目光投向 existing designs,从而引出了计算机理论科学中最出名,最基本,最引人浮想联翩且至今仍悬而未决的问题(the central question):Does P = NP ?

  • If P == NP... Polynomial-time algorithms for SAT, ILP, TSP, FACTOR, RSA, Diffie-Hellman... Most existing rules will collapse.
  • If P ≠\neq NP... Would learn something fundamental about our universe.
  • Overwhelming consensus: P ≠\neq NP.

为什么人们普遍相信 P ≠\neq NP? 因为对于人类而言,验证一个某个问题解的正确性通常比解决某个问题简单许多。欣赏一首乐曲比创造一首乐曲更容易;验证一个定律比提出一个定律更容易,使用一个装置比发明一个装置更容易……如果 P == NP,人类在经验主义下得到的这些结论将会被彻底的颠覆。

反證法。設 P = NP。令 y 為一個 P = NP 的證明。證明y可以用一個合格的電腦科學家在多項式時間內驗證,我們認定這樣的科學家的存在性為真,但因為 P = NP,該證明y可在多項式時間內由這樣的科學家發現,但是這樣的發現還沒有發生(雖然這樣的科學家試圖發現這樣的一個證明),我們得到矛盾。

NP-Completeness

Def. An NP problem is NP-complete if every problem in NP poly-time reduce to it.

Proposition. [Cook 1971, Levin 1973] SAT is NP-complete.

Extremely brief proof sketch.

  • Convert non-deterministic TM notation to SAT notation.
  • If you can solve SAT, you can solve any problem in NP.

这是一个非常重要的发现:SAT 从此成为了 NP 问题的核心,弱点;攻破了它就相当于解决了 P == NP 问题。

  • SAT captures difficulty of whole class NP.
  • Poly-time algorithm for SAT iff P == NP.
  • No poly-time algorithm for some NP problem →\to none for SAT.

Cook-Levin's problems: more poly-time reductions to SAT

在 intractability 一节中,我们介绍由 Karp 发现的一系列问题(Karp's problems),它们均能够 reduce from SAT(箭头由 SAT 出发);而 Cook-Levin 所发现的 SAT 的 NP-completeness 性质则告诉我们所有的 NP 问题均能 reduce to SAT(箭头指向 SAT)。

结合 Karp 与 Cook-Levin 的理论,我们可以得到另一个重要的发现:所有的 Karp's problems 均能与 SAT 互相 poly-time reduce,因此它们是等价的;这意味着 Every Karp's problem is NP-complete. 或者这么说:We can replace SAT with any of Karp's problems.

Karp's problems: SAT, ILP, HAMILTON-PATH, 3D-ISING, 3-COLOR, SUBSET-SUM...

我们再次对已经 cover 的概念进行总结:

  • P. Class of search problems solvable in poly-time (on deterministic TM).
  • NP. Class of all search problems, some of which seem wickedly hard.
  • NP-complete. Hardest problems in NP.
  • Intractable. Problems with no poly-time algorithm.

Coping with Intractability

如何解决 intractability?一个具有 intractability 性质的问题一定没有应用价值吗?

Exploiting intractability.

  • 事实上,现代加密学的可靠性几乎全部建立在某些问题的 intractability 上 [具体请食用 COMP3357 的 hard problems 一节],包括 FACTOR, RSA, DLOG 与 Diffie-Hellman 等等。
  • [Shor 1994] 量子计算机能够在 n3n^3 步内 factor an nn-bit integer - 我们还能相信 extended Church-Turing thesis 吗?

Coping with intractability.

  • Solve arbitrary instances of the program: special cases may be tractable.
  • Solve the problem to optimality: 采取近似 non-determinism 的方法;develop a heuristic/approximation algorithm, and hope it produces a good solution.
  • Solve the problem in poly-time in pratical case.

课程尾声

That's all, folks: just keep searching!

[2023.9.2 - 23:19] 最感动的一集。风雨阵阵敲打着窗户,俏皮欢快的 Find the Longest Path 从电脑中传出,紧随其后的是 Sedgewick 教授潇洒的挥手告别。我无比庆幸这个世界是 P≠NPP\neq NP 的,若非如此,找到人生的 longest path 将不费吹灰之力;那该是一个多么无聊的世界!

CC BY-NC-SA 4.0
正在加载评论…