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

首先回顾 $\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$

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

首先有定义 $\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$