$\mathbf{NP}$ 是用最坏复杂性定义的：一个语言 $L\in\{0,1\}^*$, 如果存在一个 NTM, 能在多项式时间内运行完毕，接受任意 YES instance 并拒绝所有 NO instance, 那么称 $L$ 是 $\mathbf{NP}$ 语言. 注意我们对 NO instance 也有多项式时间的要求.

实际中我们有时候不关心最坏情况，而关心平均情况.

Distributional Problems

例1. $CLIQUE=\{\langle G,k\rangle:\exists K_k\subset G\}$ 是一个 $\mathbf{NP}$-complete 问题，可用 $3SAT$ 或者 $VERTEXCOVER$ 归约.

复习一下 $CLIQUE$ 难于 $VERTEXCOVER$:

Pf. 给定一个 instance $\langle G,k\rangle$, 目标输出 $G$ 是否有大小为 $k$ 的顶点覆盖.

如果 $G$ 有一个大小为 $k$ 的 vertex cover, 那么这个顶点集的补集一定是独立集（否则一定有边没有被覆盖到）. 反之某个独立集补集的诱导子图也一定是顶点覆盖.

所以直接把 $\langle\overline{G},n-k\rangle$ 喂给 oracle 即可.

一个直接的问题是对于一个随机图 $\mathcal{G}_{n,\frac{1}{2}}$, 给定 $k(n)$, 询问是否有这样大小的团. Erdös 说随机图中, 极大团的大小大概率是 $2\log{n}$ 左右，也可以参考这篇 lecnote.

motivation: 考虑某个 $\mathbf{NP}$ 语言 $L$，它的定义为对任意一个 instance $x$, 存在一个多项式 $p$ 和一个 verifier $V$，$x\in L\iff \exists u\in\{0,1\}^{p(|x|)}, V(x,u)=1$.

例如 $INDSET=\{\langle G,k\rangle:G\text{ has an independent set of size }=k\}$ 是一个 $\mathbf{NP}$ 语言，因为取 witness 为某个大于 $k$ 的独立集即可验证.

然而有些语言不够，例如 $ALPHA=\{\langle G,k\rangle:\alpha(G)=k\}$, 一个足够的 witness 不仅仅要给出一个 $k$-独立集，还要让 verifier 相信大于 $k$ 的顶点集都不独立. 后者所需的长度至多是 ${n\choose k+1}$ (因为只需要看 $k+1$ 子集就行了).

我们需要更强的描述！

Polynomial Hierarchy

$ALPHA\in\mathbf{\Sigma}_2^p$, 一个 verifier 只需要 check 输入的两个 witness $S_1$ 是 $k$ 独立集、$S_2$ 是 $k+1$ 非独立即可.

观察定义，可以看到 $\mathbf{NP}\cup\mathbf{coNP}\subset\mathbf{\Sigma}_2^p$, 因此 $\mathbf{\Sigma}$ 是 $\mathbf{NP}$ 的扩充, $\mathbf{\Sigma}_1^p=\mathbf{NP}$, $\mathbf{\Pi}_1^p=\mathbf{coNP}$. 或许也可以说 $\mathbf{\Sigma}_0^p=\mathbf{\Pi}_0^p=\mathbf{P}$.

之前计算理论的坑还没填完.. 但是后面很多内容都在这本复杂性里面，于是先看这个了

Hierarchy, Diagonalization (and its limitations), Circuit Complexity forms the Chapter 9 INTRACTABILITY in Sipser’s book🤣

先挂一张 reduction graph

首先将判定问题扩展到搜索问题.

回顾我们是怎么证 $SAT$ 为 $\mathbf{NP}$-hard 的, 是假设给到了任意一个 $\mathbf{NP}$ 语言, 根据这个语言造一个逻辑表达式. 由于 $L$ 是 $\mathbf{NP}$ 的，一定存在确定性图灵机 $M$，使得 $x\in L\iff\exists u\in\{0,1\}^{\text{poly}(x)},\;M(x,u)=1$. 我们构造一个逻辑表达式，它描述了图灵机 $M$ 每一步的状态直到接受，所需满足的条件. （有一个细节，我们需要根据原来的图灵机构造一个 $2$ 纸带图灵机，有一条是只读带，而且图灵机的指针移动和输入内容无关，只和输入长度有关，这样的图灵机称为 Oblivious TM）. 这样一来，逻辑表达式只需要描述 $4$ 个条件：

• 输入的前 $n$ 位等于 $x$
• 初始状态
• 对于每一个时间步，符合图灵机运行规则
• 结束状态，在接受态停机

这样的一个归约函数 $f$ 不仅满足 $x\in L\iff f(x)=1$, 而且将 $x$ 的一个 witness 转换成了逻辑表达式的一个赋值. 同时，由于这个逻辑公式完全符合图灵机的运行情况，一个使表达式为真的赋值也对应了一个 witness. 这样的归约称为 Levin reduction, 可被用于搜索问题上（搜索问题就是找到一个 witness）.

…ようこそ。Ave Mujicaの世界へ

2025 冬休み

Chapter 1 正则语言

定义. 有限自动机，(deterministic) finite automaton (pl.-ta) (DFA)
有限自动机是一个五元组$(Q,\Sigma,\delta,q_0,F)$：
$Q$ - 有限状态集
$\Sigma$ - 有限字符集
$\delta:Q\times\Sigma\mapsto Q$ - 转移函数
$q_0\in Q$ - 初始状态
$F\subseteq Q$ - 接受状态集合

语言是字符串的集合，即 $\Sigma^*\cup\{\epsilon\}$ 的子集. 一个有限自动机所接受的所有字符串集合也是一个语言，记作 $L(M)$ . 需要特别注意语言 $\varnothing$ 和字符串 $\epsilon$ 的区别.

定义. 正则语言，regular language
对于语言 $A$，如果存在自动机 $M$ 使得 $L(M)=A$，那么 $A$ 是正则语言。

定义. 正则运算，regular operation
对语言 $A,B$， 定义
$A\cup B=\{x:x\in A\text{ or }x\in B\}$,
$A\circ B=\{xy:x\in A\text{ and }y\in B\}$,
$A^*=\{x_1\dots x_k:k\geq 0, \forall i\;x_i\in A\}$