第七章：时间复杂性
Contents
7 Time Complexity
关于其他章节的内容，请点这：《计算理论导引》学习笔记
7.1 Measuring Complexity
大O表示法
跟CLRS里的套路一样的，此处略去。。。
时间复杂性类
Let \( t: N \longrightarrow R^+\) be a function. Define the time complexity class, TIME(t(n)), to be the collection of all languages that are decidable by an O(t(n)) time Turing machine
注意：
一个语言的时间复杂性很依赖于所选用的模型，用单带、多带、非确定性图灵机来解决问题所需的时间一般都是不同的
与之相反，一个语言的可判定性对模型的依赖性不大：
In computability theory, the Church-Turing thesis implies that all reasonable models of computation are equivalent–that is, they all decide the same class of language.
Fortunately,time requirements don’t differ greatly for typical deterministic models.
例如，多带图灵机的时间复杂度最多是单带图灵机的平方：
定理7.0
Let t(n) be a function, where \( t(n) \ge n\). Then every t(n) time multitape Turing machine has an equivalent \( O(t^2(n))\) time single-tape Turing machine.
证明略。。。
相反，确定性图灵机的时间复杂度是非确定性图灵机的指数倍
定理7.1
Let t(n) be a function, where \( t(n) \ge n\). Then every t(n) time nondeterministic single-tape Turing machine has an equivalent \( 2^{O(t(n))}\) time deterministic single tape Turing machine
证明略。。。不过要明确一点：非确定性图灵机的时间负责度指的是其中一个运行最久分支，因为分支是并行进行的
7.2 The Class P
多项式等价
All reasonable deterministic computational models are polynomially equivalent.
(We don’t attempt to define reasonable.However, we have in mind a notion broad enough to include models that closely approximate running times on actual computers.)
例如上面说的单带图灵机与多带图灵机就是多项式等价的
P类
p is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.
In other words, \( P = \bigcup\limits_k TIME(n^k)\).
The class P plays a central role in our theory and is important because
1.P is invariant for all models of computation that are polynomially equivalent to the deterministic single-tape Turing machine, and
2.P roughly corresponds to the class of problems that are realistically solvable on a computer.
例子
欧几里得算法
注意，对于一个数字N，<N>一般是指N的二进制形式（或者其他进制）
图灵机的时间复杂度的输入规模衡量标准一般是输入的长度
所以欧几里得算法是线性的
CFL
Every context-free language is a member of P.
前面证明CFL可判定时用的算法是指数型的，这里要用DP证，略。。。
7.3 The Class NP
从这节开始，书中出现了大量的we don’t know 🙂
比如“有很多问题，我们不知道是否能在线性时间内解决”
polynomial verifiability
哈密顿问题
证明一个图有哈密顿回路（每个点都只经过一次）
对于这个问题，我们不知道能否在线性时间内解决，但我们能在线性时间内验证(polynomial verifiability)
也就是说，给定一个图，如果再给定它的一条哈密顿回路，这条回路就是一个证据(certificate)
我们首先要验证(verify)这个证据的真假，如果这个证据是真的，那么我们就证明了给定的图有哈密顿回路
能在线性时间内验证证据的真假就叫做polynomial verifiability
相反，假设我们要证明一个图没有哈密顿回路
那我们的证据就必须是所有回路
而一个图的所有回路的数量是指数级的，所以我们不能在线性时间内验证
NP类
定义
The term NP comes from nondeterministic polynomial time
NP is the class of languages that have polynomial time verifiers
A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine.
也就是说：能在线性时间验证 \( \iff\) 属于NP类 \( \iff\) 能被非确定性图灵机判定
取一边为NP的定义，另一边就是要证明的定理，证明的关键是：
We show how to convert a polynomial time verifier to an equivalent polynomial time NTM and vice versa.
The NTM simulates the verifier by guessing the certificate.
The verifier simulates the NTM by using the accepting branch as the certificate.
具体而言：
N = “On input w of length n:
1.Nondeterministically select string c of length at most \( n^k\).
2.Run V on input <w,c>
3.If V accepts, accept; otherwise, reject.”
V = “On input <w,c>, where w and c are strings:
1.Simulate N on input w, treating each symbol of c as a description of the nondeterministic choice to make at each step.
2.If this branch of N’s computation accepts, accept; otherwise, reject.”
NTIME(t(n))
类似TIME(t(n))，我们还可以定义NTIME(t(n))
NTIME(t(n)) = {L | L is a language decided by an O(t(n)) time nondeterministic Turing machine}.
于是，\( NP = \bigcup\limits_k NTIME(n^k)\).
NP=P?
欢迎来到CS里最伟大的we don’t know之一：NP=P?
P = the class of languages for which membership can be decided quickly.
NP = the class of languages for which membership can be verified quickly.
这是一个很纠结的问题
验证总比解决容易吧，常理来说应该是不等的，很多NP问题至今也没有找到线性解
但这就意味着很多问题不可能被高效解决，这对于研究算法的人来说，是很不爽的
7.4 NP-completeness
completeness
一个NP-completeness问题有线性解 \( \longrightarrow\) NP=P
484掉渣天
未完待续。。。ORZ