---
url: /weekly/week4/index.md
---
## Abstract

本周主要完成了两篇论文的阅读工作，一篇来自图算法领域，讲述如何在符号二部图中枚举所有极大平衡符号双团；另一篇来自大语言智能体领域，利用两个智能体协同机制，改进物品推荐算法。

相应地，针对上次汇报中对 P 问题了解不足的问题，通过询问 LLM 和查阅相关文章的方式，对 P 问题相关概念有了比较清晰的认知，学习到了如何证明一个问题是 NP 的、NP-hard 的、NPC 的。

## Main Work

### What I have read

1. 《Maximal Balanced Signed Biclique Enumeration in Signed Bipartite Graphs》
2. 《Agentic Feedback Loop Modeling Improves Recommendation and User Simulation》

### What I have learned

#### [P、NP、NPC、NP-hard 问题](../blog/Algorithm/P-NP-NPC.md)

整理了 P 相关的基本概念：从 P 问题（多项式时间内能解决的问题）出发，NP 是能在多项式时间内验证的问题，NPC 是所有 NP 问题都在多项式时间内能约化到的 NP 问题，NP-hard 问题是所有问题都能在多项式时间内约化到的问题。

约化的核心是**构造两个问题输入和解之间的转化**。即寻找两个高效算法 $\sigma,\tau$，使得 $\sigma$ 将问题 A 的输入变化到问题 B 的输入，$\tau$ 将问题 B 的解变化到问题 A 的解。

**如何证明属于 NP 和证明 NP-hard？**

设待证明的问题为 $X$。

| 要证明的性质      | 常用证明方法                                                      | 使用约化时的方向                                    |
| ----------------- | ----------------------------------------------------------------- | --------------------------------------------------- |
| $X\in\mathrm{NP}$ | 构造多项式时间验证器，并证明证书[^证书]长度受输入长度的多项式限制 | 将 $X$ 约化到某个已知属于 NP 的问题 $Y$：$X\le\_p Y$ |
| $X$ 是 NP-hard    | 将某个已知 NP-hard 的问题 $H$ 约化到 $X$；通常选已知 NPC          | $H\le\_p X$                                          |
| $X$ 是 NPC        | 同时证明上述两项                                                  | 两项都需要                                          |

[^证书]: “证书”（certificate），也称“见证”（witness），是用来证明某个判定问题实例的答案为“是”的一份辅助信息。验证算法拿到这份信息后，就能检查它是否确实支持“是”这个答案。

其中，证明 $X\in\mathrm{NP}$ 时，“验证器”的要求是：对每个答案为“是”的实例，存在一个多项式长度的证书能使验证器接受；对每个答案为“否”的实例，不存在任何符合长度限制的证书能使验证器接受[^NP的定义与NP完全性的证明方法]。NP 的定义要求 *“是”实例* 有可快速验证的证书，并不要求 *“否”实例* 也有这样的证书。

[^NP的定义与NP完全性的证明方法]: [康奈尔大学讲义，NP的定义与NP完全性的证明方法]\(https://www.cs.cornell.edu/courses/cs4820/2013sp/Handouts/reductions.pdf\)，§4,5.

::: note 为什么证明 NP-hard 时，方向必须反过来？

$$
A\le\_p B
$$

表示：可以在多项式时间内，把 $A$ 的实例转换为 $B$ 的实例，使得**求解 $B$ 就能用来求解 $A$**。所以，如果已经知道 $A$ 很难，就可以借此证明 $B$ 至少具有 $A$ 的难度。严格来说，约化函数 $f$ 必须满足：

$$
x\text{ 是 }A\text{ 的“是”实例}
\iff
f(x)\text{ 是 }B\text{ 的“是”实例},
$$

且 $f$ 的计算时间是输入长度的多项式。

例如，以已知 NP 完全问题 SAT(Boolean Satisfiablity Problem,布尔可满足性问题,SAT)\[^SAT] 为参照：

\[^SAT]: 给定布尔表达式，是否存在对变量 `True` 或 `False` 的赋值，使得整个表达式为 `True`。

$$
X\le\_p\mathrm{SAT}\quad\Longrightarrow\quad X\in\mathrm{NP},
$$

$$
\mathrm{SAT}\le\_p X\quad\Longrightarrow\quad X\in\text{NP-hard}.
$$

这两条放在一起，也就能证明 $X$ 是 NP 完全问题。
:::

> **NP 完全问题类是 NP 问题类与 NP-hard 问题类的交集。对于判定问题，在多项式时间多对一约化的意义下，证明一个问题属于 NP，通常通过构造多项式时间验证器，并说明证书长度受输入长度的多项式限制；也可以将该问题约化到一个已知属于 NP 的问题。证明一个问题是 NP-hard，则可以将某个已知 NP-hard 的问题（通常选取 NP 完全问题）约化到该问题。若同时证明该问题属于 NP 且是 NP-hard，就证明了它是 NP 完全问题。**

#### 算法优化的思路

从现有算法的局限性出发，针对每一条局限性讨论优化方法。

1. 搜索空间大 $\rightarrow$ 寻找候选点满足的必要条件进行剪枝；
2. 访问顺序对效率影响大 $\rightarrow$ 寻找合适的访问顺序，设计针对性指标进行评价；

针对剪枝算法，考虑剪枝效率，先进行大幅度筛选、时间复杂度较低的剪枝技术，在初筛之后设计精细的、复杂度稍高的剪枝方法达成更优的剪枝效果。

#### 实验设计方面

一般来说，实验设计需要考虑以下几个方面：

1. **实验因素**。重点考察的实验因素是什么？哪些因素对实验结果起较大的影响；
2. **评价指标**。选用什么作为实验单位，实验效应应通过哪些观测指标来体现；
3. **实验误差**。选用什么样的实验设计方案来控制重要的非实验因素的影响，以便有效地控制和估计实验误差；
4. **组分分析**。设计消融实验，以验证所提出的新结构在设计目标上的有效性。

## Future Work

1. 继续推进论文阅读，阅读社会计算领域综述文章，构建对整个领域的初步了解；
2. 学习 Agent Kernel 相关知识。