ITCS

快到期末周了，为自己的Cheat Sheet做点准备

Naive Set Theory

感觉唯一要看的是两个集合的power和一个证明过程。

CaO，一翻Slide发现还有几个定义要说。

几个定义

$\binom{A}{k}={X $ $\subseteq A: |X|=k\}$

$B^A=\{f: A\to B\}$

$a\quad R \quad b$ infixnotation for $(a,b)\in R$

一个证明

Theorem: For every set $A$ it is not the case that $|2^A|\le |A|$

Proof: $h$$:\to$$2^A$, we need to show that $h$ is not a surjection.

i.e. given $h$ we need to find some $\Delta_h\in 2^A$ so that

$$\forall a\in A:h(a)\ne \Delta_h$$

Use $\Delta_h=\{a\in A|a\not \in h(a)\}$

For every $a\in A$ the sets $h(a)$ and $\Delta_h$ differ in element $a$.

经典方法

康托对角化

Words, Strings, Language

一些定义

$\Sigma\dots$ finitset “Alphabet”

$\Sigma^k\dots$ ordered k-tuples over $\Sigma$ $\quad w=(a_1,a_2,\dots,a_k)$

$\quad\quad\quad$words of length $k\quad$ $w=a_1a_2\dots a_k \qquad |w|=k$

$\epsilon \qquad$ empty word

$\Sigma^*\quad \Sigma^+$ all finite string and all finite non-empty string

$\#_a(w):$ a在w中的出现次数

$L\subset \Sigma^*\dots$ “language” over $\Sigma$

图灵机入门

三类： FA，PDA，TM

分别对应Chomsky的 Regular grammar，Context free grammar和Unrestricted Grammar

FA

记号

$\Sigma\quad Q\quad s\in Q\quad F\subset Q\quad \Delta \subset ((Q\times\Sigma)\times Q)$

分别代表： 字符集 状态集 起始状态 终止状态集 Configuration(状态转移路径集？)：(当前状态，转移字符，转移后状态)

Computing step relation $\vdash_M$ on $K_M$

$\forall q\in Q, a\in\Sigma, u\in\Sigma^*: (q,au)\vdash_M(q',u) \text{ iff } (q,a,q')\in\Delta$

$\vdash_M^*$ on $K_M$

当有一个计算路径时，直接前面起始state，后面终止state.

分为Deterministic 和 Non deterministic.

Continuous Language

是这门课教授为了教学创造的概念，但给的Lemma是通用的

定义为 $F_L(w)=\{a|a\in\Sigma,wa\in L\}$

Theorem(Myhill-Nerode)

L DFA language $\iff \mathcal{F}_L$ is finite

一般反着用：

$\mathcal{F}_L$ not finite $\implies$ L not DFA-language.

证非REG可以找一组 $\{w^{(i)}\in\Sigma^*\}$ s.t

$$F_L(w^{(i)})\ne F_L(w^{(j)}) \text{for } i\ne j$$

之后有Pumping Lemma了其实就没那么常用了。
后面也知道DFA-language就是Regular Language

DFS Minimization

暴力算法：先按终态和末态分，然后每次检查每个划分中是否每个元素在每个可能输入下都会保持在同一分区，如果不是，将输入后的转移结果相同的状态再划分到一起

NFA转DFA

因为我一直和最小化搞混，就一起写了。
子集构造好难。

定义：子集构造就是先对Q做一个powerset，然后将里面的元素作为新的Q’.再按这些子集之间的转移关系建立新的DFA。

哎，期中考试这题一分不得。麻了。

Pumping Lemma

正着的形式：
L REG $\implies$
$\exists N\in \mathbb{N}: \forall uvw\in L\qquad\exists \text{partition } v=xyz\quad :\forall i\in \mathbb{N}:uxy^izw\in L$

$\qquad\qquad\quad\quad|v|\ge N \qquad\quad\qquad\text{with}0<|y|\le N$

因为它是必要不充分的，一般反着用判断非REG：
Remark: 对于 over 一个字母的language，fulfilling the pumping lemma is 充要的 （我在写什么，蚌）

$\forall N\in\mathbb{N}:\exists uvw\in L\quad:\forall \text{partition } v=xyz\quad:\exists i\in\mathbb{N}:uxy^iz\not\in L$

$\qquad\qquad\quad\quad|v|\ge N \qquad\quad\qquad\text{with}0<|y|\le N$

可以用一种“玩游戏”的说法解释一下全称量词：

$\forall$对手选，自己无法控制
$\exists$自己选

1. 对手选$N$，你母鸡
2. 自己从L中选一个词，并自己确定uvw的划分，$|v|\ge N$
3. 对手选择v=xyz的划分方法，保证 $0<|y|\le N$
4. 自己选择$i$使$uxy^izw$不在L中

这样就可以证L非REG了。

PDA

Notations

比FA多了:

1. $:栈的起始符号
2. $\Gamma$:栈的字符集
3. $\Delta$ 多一个对栈的操作，变为$((Q\times \Sigma\times\Gamma)\times (Q'\times \Gamma'))$

以及有两种接收状态，final-state 或者 empty stack。

Pumping Lemma for CFL

相似地，对于Context Free Language， 我们也有相似的Pumping Lemma。

基本思想可以近似地理解为因为生成规则是finite的，因此想要生成长字符串必定能有某种重复规律。

Formally:

$\exists z\in L, |Z|\ge N$
$\forall$ partition z=uvwyz with $|vwx|\le N, |vx| >0$
$\exists i \text{ s.t. } uv^iwy^iz\not\in L$

主要是第二步要分类讨论，覆盖所有可能情况。

以及one letter alphabet满足pumping lemma后还regular。

Closure Property

Give that $L,L'$ to be context-free language and $R$ to be regular language, we have the following are also context-free:

1. $L\cup L'$
2. $L\cdot L'=\{xy|x\in L \text{ and }y\in L'\}$ (Concatenation)
3. $L^{Rev}=\{x^{Rev}|x\in L\}$ (Reversion)
4. $L^i=L\cdot L^{i-1} \text{ for } i>0, L^0=\{\epsilon\}$
5. $L^*$
6. $L\cap R$

然后以下两个not necessarily context-free:

1. $L\cap L'$
2. $\overline{L}$

Proof 1)

$L=\{a^ib^jc^k|i,j,k\in\mathbb{N},i=j\}$
$L'=\{a^ib^jc^k|i,j,k\in\mathbb{N},i=j\}$
$L\cap L'=\{a^ib^jc^k|i,j,k\in\mathbb{N},i=j=k\}=\{a^nb^nc^n|n\in\mathbb{N}\}$
which is not context-free by the pumping lemma for CFL.

Proof 2)

Assume it’s true, we have $L\cup L'=\overline{L\cap L'}$.

But we have proofed the right hand side to be not necessarily context free. Thus the statement is also not necessarily true.

注意CFL是NPDA language，后面讨论DPDA和NPDA时候要区分清楚。

DPDA和NPDA的能力区别

• Theorem： DPDA are closed under complement.

证明大体思路是对$L$构造一个DPDA $M$, 然后吧所有的Final state和non-final state flip一下。

然后几个构造的点要注意：

1. 对所有的Dead end建一个超级死点（， 这样保证取反后能到，而且是final sate
2. 提前计算$\epsilon$闭包，保证最后$\epsilon$-move 的结果是确定的，避免$\epsilon$-move随便带到final或者non-final state。

有了这个结论，我们就能对这两种machine的能力做个总结了：

• DPDA language$\subseteq$NPDA language

因为NPDA language不能取补集，而DPDA可以，因此NPDA包含的语言更多。

更进一步还有什么结论呢？

• 如果$L$accepted by some PDA $M$, then it is also accepted via empty stack by some NPDA $M'$ with only one state.

这时候，栈顶元素就代表着现在的state。

Grammar

符号定义

$G=(\Sigma,V,S,P)$

• $\Sigma$: terminal alphabet
• $V$: variable alphabet
• $S\in V$: start variable
• $P\subset FVF\times F$, ($F=(\Sigma\cup V)^*$)

这些集合都是finite的。

$\Rightarrow_G^*$是reflexive， transitive closure of $\Rightarrow_G$: derivation relation on F.

The language generated by $G$ is:

$$L(G)=\{w\in\Sigma^*|S\Rightarrow_G^*w\}$$

🌰

生成$L(G)=\{a^nb^nc^n|n\in\mathbb{N}\}$的Grammar：

• $V=\{C,D,S\}$
• $\Sigma=\{a,b,c\}$
• $\begin{aligned} P=\{S&\rightarrow aDbc,S\rightarrow\epsilon,\\ D&\rightarrow aDbc,D\rightarrow\epsilon,\\ C&b\rightarrow bC,\\ C&c\rightarrow cc\} \end{aligned}$

Chomsky之你第一次听说他是在哪里（

• Type 0 (unrestricted)
• Type 1 (context sensitive) only productions $\alpha\rightarrow\beta$ where $|\alpha|\leq|\beta|$
  也就是说语法不能缩短字符串
• Type 2 (context free) only production of the form $A\rightarrow a$ where $A\in V$
  意思是生成只需要非终结符，无关上下文
• Type 3 (right linear=regular language)
  只能以下form
  $A\rightarrow uB,A\rightarrow u,A\rightarrow \epsilon$ where $A,B\in V$ and $u\in\Sigma$

唯一需要注意图灵机对应的是type1对应TM with linearly bounded work space.

Context free grammar的条件

1. 存在derivation
2. 存在leftmost derivation
3. 存在derivation tree with $\alpha$ as leaf labelling

Normal Form (for context-free grammar)

CNF

Have the form $A\rightarrow a$ or $A\rightarrow BC$ ($A,B,C\in V$ and $a\in\Sigma$)

GNF

Have the form $A\rightarrow aU$, ($U\in V^*,a\in\Sigma$)

TM

STM的formal specification

有几个新记号：

• $\#\in\Gamma\setminus\Sigma$
• $\Delta\subset (Q\times\Gamma)\times(Q\times\Gamma\times\{-,0,+\})$ computation

然后Linearly Bounded Automata就是只用input tape的STM。

更Generalized的TM

主要是computing step rules, $\Delta\subset (Q\times\Sigma\times\Gamma^k)\times(Q\times\{-,0,+\}\times(\Gamma\times\{-,0,+\})^*)$

DTM与NTM等价。

Church-Turing Thesis

Everything that is computable at all can be computed by a Turing machine.

从Computable到Decidable

partial function f computable

给定TM $\mathcal{M}$, $\forall x\in\Sigma^*$,upon input $x$：

• stops with tape content $f(x)\in\Gamma^*$ in case $f(x)$ is defined.
• and does not stop in case $f(x)$ is not defined.

然后everywhere computable就是$f(x)$对$\forall x\in \Sigma^*$有定义。

Recursively Enumerable

$A\subset \Sigma^*$ r.e. $\implies$ there is an everywhere computable 的 function $F:\mathbb{N}\to \Sigma^*$ so that

$$A=\{F(1),F(2),\cdots\}=\{F(n)|n\in\mathbb{N}\}$$

Decidable

首先给一个characteristic function的定义：

$A\subset\Sigma^*$, 那么

$$\chi_A(x)=\begin{cases} 1, \text{if x$\in$ A}\\ 0, \text{if x$\not \in$ A} \end{cases}$$

就是characteristic function.

我们定义Semi-decidble为只用对$x\in A$的情况有定义就可以。

然后如果 $A$ decidable, 那么我们有 $A$ semi-decidable 和 $\overline{A}$ semi-decidable。然后这里语言decidable也包含对应的Turing Machine acceptable。

TM’s encoding

$$\begin{aligned} M =& (\Sigma, \Gamma, \#, Q, s, F, \Delta)\\ \Sigma =& \{ a_2, \ldots, a_t \}\\ \Gamma =& \{ a_1, \ldots, a_t, \ldots, a_g \}\\\# =& a_1\\ Q =& \{ q_1, \ldots, q_m \}\\s =& q_1\\F =& \{ q_2 \}\\ \Delta \subseteq& (Q \times \Gamma) \times (Q \times \Gamma \times \{ -, 0, + \})\\\Delta =& \{ \delta_1, \ldots, \delta_D \}\\\text{-} =& \mu_1,\quad \text{0} = \mu_2,\quad \text{+} = \mu_3\\cod(M)=&cod(\delta_1)cod(\delta_2)\cdots cod(\delta_D)\\ cod((q_h,a_i,q_j,a_k,\mu _p))=&01^h01^i01^j01^k01^p0 \end{aligned}$$

这样我们就能引入UNIV和SAM的问题，因而探索NP，P之类的问题。

SAM： Self Accepting Machine， 能否accpet自己的编码。
UNIV：给定任意一个图灵机$M$的编码，能否模拟它。

SAM相关

这里，UNIV是Turing acceptable但不是decidable的。

然后SAM是undecidable的，简单的证明如下：

先证$\overline{\textrm{SAM}}$undecided：

要证 no TM $\mathcal{M}$ where $L(M)=\overline{\textrm{SAM}}$.
For every TM $\mathcal{M}$ we have $L(M)\not=\overline{\textrm{SAM}}$
For every $w\in\{0,1\}^*$ we have $L(M_w)\not=\overline{\textrm{SAM}}$

$L(M_w)$ and $\overline{\textrm{SAM}}$ differ at least in $w$ thus $w\not\in L(M_w)\Leftrightarrow w\in\overline{\textrm{SAM}}$

然后再证$\textrm{SAM}$undecidable。
假设$\textrm{SAM}$decidable, 那么

• SAM TM acceptable and
• $\overline{\textrm{SAM}}$ TN acceptable, which is not。

从这个证明过程中可以学到我们可以先证一半not TM acceptable，再用定义推出整个undecidable.

UNIV相关

UNIV是undecidable的，因为我们可以使用$\textrm{SAM}$构造一个UNIV, 然后 $\textrm{SAM}$已经被证明undecidable了，说明UNIV至少和它一样难，因此它也undecidable.这就引出了我们接下来Reducibility的概念。

Reducibility

基本定义

不formal的定义：A$\preceq$B，说明：

• B decidable，因为A不会更难，因此A decidable。
• A undecidable, 因为B至少和A一样难，因此B undecidable.

经典停机问题解法：
SAM$\preceq$HALT

SAM(M):
   if not HALT(M,cod(M)):
       reject
   else 
       if M(cod(M)):
           accept;
        else:
           reject.

这样就构造出了SAM。而SAM undecidable。所以HALT也undecidable.

这样我们就证明了HALT undecidable.

Formal的定义：

$\forall A,B \subseteq \Sigma^*, \exists \text{ everywhere computable } f:A\to B, \forall x\in A, f(x)\in B$

虽然不知道怎么用，但还是记一下。

Rice’s theorem

令 $\mathcal{RE}$ 为所有r.e.语言构成的集合，取一个子集 $S$, $\forall S\subset \mathcal{RE}$, 这里$S$ non-trivial, 有

$$C(S)=\{w|L(M_w)\in S\}$$

undecidable。

和证伪很简单，因为只要举反例。证实很困难，因为要覆盖到（enumerate）所有情况是一个思路。

PCP problem & MPCP

$MPCP_\Sigma \preceq PCP_{\Sigma\cup \{ \$,\# \} }$

对于每个下面的元素，我们在每个字母开头加上#.
对于上面的元素，我们对于第一个元素，在它的每个字母前后都加上#,对于其他元素，只在后面加#.
最后再加一个($,#$)的骨牌。
这样就能把一个$k$张牌的MPCP归化为一个$k+1$张牌的PCP了。
因为这样保证了:

• 之前问题的第一张牌一定在第一位
• 只有在原问题有解时构造出的问题才有解。

Reduction链

$$\textrm{UNIV} \mathop{\preceq}\limits^1\textrm{WORD} \mathop{\preceq}\limits^2 \textrm{MPCP} \mathop{\preceq}\limits^3 \textrm{PCP}$$

证明如下：

1. 在证明TM和Grammar能力等价的时候证了
2. 把生成过程写出，把$\$S\Rightarrow w€$两行Reverse一下，并排放。头是$(€w,€)$,尾是$(\$,S\$)$,中间直接对应。这样就完成了构造。
3. 上面证过了。

因此我们可以说PCP undecidable.
有了这个，我们还可以证一些语言之间的关系的问题undecidable.因为这些都能归化到PCP problem。

核心思路是对一个PCP instance $(k,((x_1,y_1))\cdots,(x_k,y_k))$

Consider

$$L_X=\{I^R\$X[I]|I\in\{1,2,\cdots,k\}^+\} \\ L_X=\{I^R\$X[I]|I\in\{1,2,\cdots,k\}^+\}$$

这里$I,J$为index set，然后$I^R$为reverse一下指标集$I$.
$L_X$是Context free的，因为他可以这么生成：

$$S\to i Sx_i, 1\leq i\leq k\\ S\to i \$x_i, 1\leq i\leq k$$

这样也能更好理解为什么要对指标集取反，因为确实是和$对称的。

这样我们就能用这两个Grammar去证一些东西了，比如要证：

$$L(G_1)\cap L(G_2)=\emptyset$$

我们考虑 $L(G_1)\cap L(G_2)\not=\emptyset$, 那么就存在一个指标集$I$能满足 $X[I]=Y[I]$.是一个PCP的解。

为了一个一个证伪，我们得从对所有 $k>0$ 做PCP，而这个是not finite的，因此这个问题undecidable.

复杂度类

这是前两周的主要内容。记录一下。

基本符号表示

NSAPACE，DSAPCE，NTIME，DTIME：分别代表non-det和det的State graph中从$s\in S \to f\in F$的路径上thickness的最大值和...走过边数的最大值。

几个经典的复杂度类

$$P=\bigcup _{k>1}\textrm{DTIME}(n^k)$$

$$NP=\bigcup _{k>1}\textrm{NTIME}(n^k)$$

同理可得 PSAPCE和NPSPACE。
还有两个特殊的：

$$L=\mathrm{DSPACE}(\log n)， NL=\mathrm{NSAPCE}(\log n)$$

他们之间的关系是

$$L\subseteq NL\subseteq P\subseteq NP\subseteq DSPACE = NSPACE$$

补一个Tutorial提到的点。为什么区分NP和co-NP但不管co-P？因为其实co-P通过对输出取反就能做到，所以不用管。

以及有一种东西叫semi-polynomial的算法。
意思是它在以输入大小作为衡量尺度的时候有多项式时间解法，但如果以输入长度来看，它就是NP的。

P-reducible

Definition

首先引入一个polynomial reduction。
其实就是把everywhere computable的function f加了个“能在polynomial时间内算出”。符号长$\preceq_p$这样。

NP-hard & NP-completeness

NP-hard的定义：

For language $\textrm{S}$, $\forall L\in \mathrm{NP}, s.t. L\preceq_p S$, then S is $\textrm{NP-hard}$。

NP-complete的定义：

…, S$\in \mathrm{NP}$

解题格式

Tutorial上讲的，也不能说格式吧，就是证NP-completeness的过程。

1. 使用certificate的定义，证明这个东西是in NP的
2. 使用P-reduction，证明它是NP-hard的。

然后就能证好了。

常用的感觉就是：

1. $\mathrm{SUBSETSUM}$
2. $\mathrm{SAT/3-SAT}$

几个具体🌰

$\textrm{MERF}$:multi-valued satisfiability.

$$\textrm{P-UNIV}\preceq_p\textrm{MERF}\preceq_p\textrm{SMERF}\preceq_p\textrm{SAT}\preceq_p\textrm{3-SAT}\preceq_p\textrm{CLIQUE}$$

同时还有：

$$\textrm{3-SAT}\preceq_p\textrm{3COLORABILITY}$$

这个Reduction的Idea是我们把
对于$\textrm{SAT}\preceq_p\textrm{3-SAT}$这一块，记录一下教材上的证法：

对于一个柿子，比如 $p=a\land \overline{b}\land \overline{c}\land d$
我们可以引入一个新变量$z$,构造另外两个柿子$p_1=a\land \overline{b}\land z,p_2=\overline{c}\land d\land \overline{z}$。
保证只有$p$成立时，两个柿子才成立，vice versa。
这个构造可以成立的原因有两个：
1.这个构造把柿子拆成了两部分，分别和原柿子相符。
2.因为一个z取反了，另一个没有，所以整个柿子是否satisfiable与$z$无关。
因此这个构造可行。

Formal一点的写法

给出那个everywhere computable的function $f$ 的实现。

课上例子

Art Gallery Problem

问题描述是给定一个多边形，求最少需要几个“Guard”能看到所有的顶点。这个问题是NP-complete的。

几个Claim：

1. 这个东西的下界是$\lfloor\frac{n}{3}\rfloor$，可以用基本所有的polygon都能triangulation然后能3-COLOR以及triangulation总存在来证。
2. 对任意整数$k$，总存在一个有$3k^2+2$的多边形使得所需的守卫数至少为$k$。

贴一个我看起来比较好的证明.

Schönhardt’s polyhedron

以上的问题还有对应的三维版本，好像所需的证明技巧类似，也是构造三角形和“niche”。最后完成证明。

贴一下论文来源.

Space Complexity

先复习一下Simple TM的定义：

几个notation：$\Sigma \quad \Gamma\quad Q\quad s\in Q\quad F\subset Q\quad \Delta\subset((Q\times\Sigma\times\Gamma)\times(Q\times\Gamma\times M_W\times M_I))$
其中 $M_W,M_I\in\{-1,0,1\}$,为work tape和input tape上的移动状况。
而$\Delta$又能拆成3个：

• $\Delta_1 (Q\times\Sigma\times\Gamma)\times(Q\times\Gamma)$ 对work tape的修改
• $\Delta_2\ (Q)\times(Q\times M_W)$ move on work tape
• $\Delta_2 (Q)\times(Q\times M_I)$ move on input tape

几个PSAPCE-Complete的🌰

• Context Sensitive Grammars
• 华容道
• graph coloring game
• …

Randomness(不考)

几个复杂度类

RP & co-RP

$L\in\mathrm{RP}$, $\exists$ TM $\mathcal{M}$ that for any input $x$, we can determine the following thing in $p(|x|)$ time where $p$ is a polynomial:

• $x\in L \to \mathcal{M}$ accept YES with Prob $\ge$ 1/2.
• $x\not\in L\to$ NO.

🌰：Miller-Rabin素性检验

BPP & ZPP

ZPP=RP $\cap$c o-RP

BPP: 错误概率小于 1/3

🌰：SAT的多项式版本

课上老师给的Big Picture

Computing

首先，给定几个基本要素：

1. Input tap, Work tape
2. FA, FDA, TM
3. (non-)deterministic

然后是几个概念：

1. grammars
2. language accepted by TM -> Recursively Enumerable
3. SAM: Self Accepting Machine
4. Reduction, 几乎是最重要的内容。

然后是Rice Theorem 和 PCP

Recursion Theory

Complexity Theory

首先复习了复杂度类的定义

Configuration Graph很重要，NP-complete的时候会argue这个东西

Poly-time reduction

默写一下定义：

$$\exists F: \Sigma^* \to \Gamma^* \text{Computable in poly-time}$$

$$\forall x\in\Sigma^*, x\in L \Leftrightarrow F(x)\in L'$$

NP-complete 定义

$$S\in \mathrm{NP}, \forall L\in\mathrm{NP},L\preceq_p S$$

还有

$$S\textrm{ NP-hard}, S\preceq_p L'\implies L' \textrm{ NP-hard}$$