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'))$

Pumping Lemma for CFL

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

基本思想可以近似地理解为因为生成规则是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$

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

Reducibility

不formal的定义：A$\preceq$B: B能解决A。B至少和A一样难。

经典停机问题解法：SAM$\preceq$HALT
SAM(M):
if not HALT(M,|M|):
reject
else
if M(|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$

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

复杂度类

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

基本符号表示

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

几个经典的复杂度类

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

$$NP=\bigcup _{k>1}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$无关。
因此这个构造可行。

课上例子

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

几个🌰

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