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 问题

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

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

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

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

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

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

为什么证明 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)^[3] 为参照：

$$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 相关知识。

---

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

2. 康奈尔大学讲义，NP的定义与NP完全性的证明方法，§4,5. ↩︎

3. 给定布尔表达式，是否存在对变量 True 或 False 的赋值，使得整个表达式为 True。 ↩︎

贡献者

Cuber-Wei

编辑此页