August 23, 2025

Randomized computation - 0x07

August 21, 2025

Something about rust compiler

Names of associated items

类方法、类中 associated const item 都属于 value namespace. 但是由于一个 struct 可以有多个 impl 块，仍然会有重名发生.

enum D {
    A,
    B,
    C,
}

impl Int for D {
    const FN: i32 = 1926;
    fn get(&self) -> i32 {
        match self {
            D::A => 1,
            D::B => 2,
            D::C => 3,
        }
    }
}

impl Str for D {
    fn get(&self) -> String {
        match self {
            D::A => String::from("A"),
            D::B => String::from("B"),
            D::C => String::from("C"),
        }
    }
}

impl D {
    fn get(&self) -> i32 {
        114514
    }
}

impl Con for D {}

struct P {}

impl Int for P {
    const FN: i32 = 2026;
    fn get(&self) -> i32 {
        1919810
    }
}

trait Int {
    const FN: i32;
    fn get(&self) -> i32;
}

trait Str {
    fn get(&self) -> String;
}

trait Con {
    const FN: i32 = 0817;
}
struct Y {
    i: i32,
    p: i32,
}

fn g(d: i32, ff: &str) -> [i32; 2] {
    let mut a = [0; 2];
    a[0] = d;
    a[1] = ff.len() as i32;
    a
}
fn main() {
    let d = D::B;
    println!("{}", D::get(&d)); // 114514
    println!("{}", Int::get(&d)); // 2
    let p = P {};
    println!("{}", Int::get(&p)); // 1919810
    println!("{}", Str::get(&d)); // B
    println!("{}", d.get()); // 114514
    println!("{}", P::FN); // 2026
    // println!("{}", D::FN); // error
    // println!("{}", Int::FN); // error
    // println!("{}", Con::FN); // error
    println!("{}", <D as Con>::FN); // 817
    println!("{}", <D as Int>::FN); // 1926
    println!(
        "{:?}",
        g({ 123 }, "Hello") // [123, 5]
    );
}

总之 1.field 和 method 可以重名；2.默认用 inherent impl 的 associated item, 它会覆盖 trait impl 的同名 item；3.如果要用 trait impl 的同名 item, 需要显式指定 trait 名.

August 20, 2025

Belief propagation

一个图模型包含 $N$ 个随机变量 $\underline{x}=(x_1,\dots,x_N)$，从有限字母表 $\mathcal{X}$ 中取值. 需要解决一些问题，例如：

给定一些条件，求另一些变量的边缘分布；
一些后验估计相关

但是我们不会去直接计算联合分布 $p(\underline{x})$，因为它的状态空间是指数级别 $|\mathcal{X}|^N$ 个取值. BP 将这个问题转化为局部计算，利用图的稀疏性/特殊结构来避免指数级别的计算.

Example 1: Ising chain

Ferromagnetic Ising model has $\underline{\sigma}=(\sigma_1,\dots, \sigma_N), \sigma_i\in\{1,-1\}$ with joint distribution

$$ \mu_\beta(\underline{\sigma}) = \frac{1}{Z} \exp\left(\beta \sum_{i=1}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^N\sigma_i\right) $$

where $Z$ is the partition function.

我们计算 $\sigma_j$ 的 marginal distribution, 这里用 $\propto$ 来省略归一化因子:

$$\mu(\sigma_j)\propto\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^N\sigma_i\right) \\=\sum_{\sigma_1,\dots,\sigma_{j-1},\sigma_{j+1},\dots,\sigma_{N}}\exp\left(\beta \sum_{i=1}^{j-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=1}^{j-1}\sigma_i\right)\exp\left(\beta\sum_{i=j}^{N-1} \sigma_i \sigma_{i+1}+\beta B\sum_{i=j+1}^{N}\sigma_i\right)\exp\left(\beta B\sigma_{j}\right)$$

分配拆开即可，是两个和的乘积. 定义 “message”:

This decomposition is interesting because the various messages can be computed iteratively.

July 18, 2025

Cyclotomic polynomial in infinite primes

下午从七分厂返回，和大 N 老师聊天提到数论，于是知道了这个证明.

Thm. For every fixed $m$, there are infinitely many prime numbers of the form $km+1$ where $k\in\mathbb{Z}$.

Lem 1. $n\gt1$, $p$ is prime, if for some $x\neq\pm1$, $p\mid\Phi_n(x)$, then either $p\mid n$, or $p\equiv_n1$.

Pf. of Lem 1. If for some $d\mid n(d\lt n)$, $p\mid x^d-1$, then $p\mid (x^d-1,\Phi_n(x))$. Since $\Phi_n(x)$ does not share any roots with $x^d-1$, we have $\Phi_n(x)\mid\frac{x^n-1}{x^d-1}$. Thus $p\mid(x^d-1,\frac{x^n-1}{x^d-1})$, where $\frac{x^n-1}{x^d-1}=\frac{(x^d-1+1)^{\frac{n}{d}}-1}{x^d-1}=A(n^d-1)+\frac{n}{d}$ (note that this requires $x^d\neq1$). Then $p\mid\frac{n}{d}\mid n$.

July 16, 2025

Average case complexity: Levin’s theory - 0x12

$\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.

July 15, 2025

The Polynomial Hierarchy and Alternations - 0x05

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}$.

July 14, 2025

Reduction & Diagonal Method - 0x03

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

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）.

July 12, 2025

Modal Logic

Intuition

Modes of Truth: 命题逻辑和谓词逻辑不允许真/假之外的可能性，然而自然语言允许。例如“永远为真”“知道为真”“相信为真”。LTL 和 CTL 就是这样的，它们是 Modal Logic 的特例。又例如对于交互式的 agent 来说，模态逻辑是一种帮助我们形式化的方法。

Our main case study will be the logic of knowledge in a multi-agent system.

Syntax

简单将谓词逻辑（即 First-Order Logic）的存在/任意，替换成 box $\Box$ 和 diamond $\Diamond$。

Semantics

模态逻辑的模型为一个 4-tuple $\mathcal{M}=(W,R,AP,L)$：

集合 $W$, 其中元素称为“世界”（这个称呼很怪，不知道是不是翻译问题，第一反应“一花一世界”）（如果称呼 $W$ 为宇宙 universe 或许说得通，事实上 Ebbinghaus 的一阶逻辑中就是这么做的）
$R\subset W\times W$ 可达关系
$AP$ 原子命题
$L:W\mapsto \mathcal{P}(AP)$ 标识函数

这里 $R$ 只是一个普通的子集，因此只能看作有向图，如果 $R(x,y)$ 那么称 $y$ 为一个可达世界.

可满足性的定义：$\mathcal{M}=(W,R,L)$, $x\in W$

$x\vdash \top$
$x\not\vdash \bot$
$x\vdash p\iff p\in L(x)$
not and or imply iff 和 FO 一样
$x\vdash p\iff p\in L(x)$
$x\vdash \Box\psi\iff\text{for all } y\in W,\;\neg R(x,y)\text{ or } y\vdash\psi$
$x\vdash \Diamond\psi\iff\text{there exists } y\in W,\;R(x,y)\text{ and } y\vdash\psi$

一些边界情况

如果 $x$ 没有可达世界，那么 $\forall\phi,\; x\vdash\Box\phi$ 且 $x\not\vdash\Diamond\phi$. 这里的 $\phi$ 也包括 $\top$ 和 $\bot$.

July 9, 2025

Properties of LLL Basis

题目摘自 Regev Hw2 的第 $4$ 题.
hw2

首先回顾 $\delta$-LLL reduced basis 的定义 ($\frac{1}{4}\leq\delta\leq1$)

Def. For linearly independent basis $b_1,\dots, b_n\in\mathbb{R}^n$, we have for all $1\leq j\lt i\leq n$, $\mu_{i,j}=\frac{\langle b_i,\tilde{b_j}\rangle}{\langle\tilde{b_j},\tilde{b_j}\rangle}$, and Gram-Schmidt orthogonalization $\tilde{b_i}=b_i-\sum_{j=1}^{i-1}\mu_{i,j}\tilde{b_j}$. Such a basis $B=\{b_1,\dots,b_n\}$ is a $\delta$-LLL reduced basis if the following holds:

Size Reduction
For all $1 \leq j \lt i \leq n$, $|\mu_{i,j}| \leq \frac{1}{2}$.
Lovász Condition
For all $1 \leq i \leq n$,
$\delta \|\tilde{b_{i}}\|^2 \leq \|\tilde{b_{i+1}} + \mu_{i+1,i} \tilde{b_i}\|^2$

July 6, 2025

Two Simple Proofs

今日不宜学习，因为两个简单的证明，没能给出完整的答案：

首先有定义 $\mathrm{decCVP}=\{(B,t,r):\mathrm{dist}(t,\mathcal{L}(B))\leq r\}$. (btr: Bocchi the Rock)

Prob1. Decisional $\mathrm{decCVP}$ is $\mathbf{NP}$-complete.

Pf. NP 类的证明比较显然，因为给一个距离小于 $r$ 的格中向量即可, 且这个向量能用多项式长度的字符串描述（其长度小于 $||t||+r$）.

NP-hard: 考虑归约 $\mathrm{decCVP}\geq_m \mathrm{SUBSETSUM}$. 给定 $\{a_1,a_2,\dots,a_n\},S$，构造格基 $v_1=(a_1,2,0,\dots),\dots,v_i=(a_i,0,\dots,2,\dots)$. 相当于 $B$ 的最上面一行是 $a_i$, 下面是 $2I$. $t=(S,1,\dots,1)$, $r=\sqrt{n}$ 即可，考虑到 $n$ 可能不是完全平方数，直接把缺少的补 $0$ 即可.

Prob2. For full rank lattice $\Lambda$, $\lambda_1(\Lambda)\lambda_n(\Lambda^*)\geq 1$.

Pf. 注意到 $\lambda_n\geq\lambda_i$, 只需找到一个 $i$ 满足即可. 设 $||v||=\lambda_1(\Lambda)$, 对于对偶格中每一个向量 $x$，都有 $\langle x,v\rangle\in\mathbb{Z}$. 我们选取 $x_1,\dots,x_n$ 使得 $||x_i||=\lambda_i(\Lambda^*)$, 那么由于满秩，不可能每个都和 $v$ 垂直，因此存在 $i$, $\langle x_i,v\rangle\geq1$, 因此，$\lambda_1(\Lambda)\lambda_n(\Lambda^*)\geq||x_n||·||v||\geq\langle x_i,v\rangle\geq 1$