难解性与 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
. - Useful in practice ("efficient") = polynomial time (
) for all inputs.
In practice,只有常数
- Factorial running time:
. - Exponential growth:
. 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
(input size = ) steps? - Given
-by- 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
这四大基本问题均属于 search problem:该类问题的重要特征之一是我们能很容易地判断某个解的正确性。以四大问题的某个解
Search problem. Given an instance
Requirement. Must be able to efficiently verify that
关于 search problem 的定义,可以看看这个帖子下的讨论。说到底这个定义并不是非常严谨,但大多数情况下我们都可以通过 common sense 来进行判断。
我们如何利用这四大基本问题来证明其他问题的 intractability?答案是通过 reduction。在目前的计算理论体系中,SAT 问题可以说是许多 intractable 问题的源头 [stay tuned for NP-completeness]。
目前来讲,对于 SAT 的一个 general instance with
基于这个 conjecture,我们可以得出这样一个结论:If SAT poly-time reduces to
Problem
- Polynomial number of standard computational steps.
- Polynomial number of calls to
.
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 这一概念存在的意义就是判断某个问题
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
NP... Would learn something fundamental about our universe. - Overwhelming consensus: P
NP.
为什么人们普遍相信 P
反證法。設 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
- SAT captures difficulty of whole class NP.
- Poly-time algorithm for SAT iff P
NP. - No poly-time algorithm for some NP problem
none for 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] 量子计算机能够在
步内 factor an -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 教授潇洒的挥手告别。我无比庆幸这个世界是

