1.0 KiB
1.0 KiB
title, created, updated, type, tags, sources, confidence
| title | created | updated | type | tags | sources | confidence | |||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Clique Decision Problem（团判定问题） | 2026-06-29 | 2026-06-29 | concept |
|
|
high |
Clique Decision Problem
safe-equilibrium-exploration 第 2 步将寻找最小 uncertain-model 的问题归约为图论中的团判定问题（给定图 G 和整数 k，判定 G 是否包含大小为 k 的团），并在多项式时间内近似求解。
归约逻辑
SEE 将模型精化建模为：在不确定性图中找一个"团"——相互兼容的模型参数集合，使得团内所有参数对可行域内数据的拟合都是"最小不确定的"。
计算性质
- Clique Decision 是 NP-完全的经典问题
- SEE 采用多项式时间近似求解
- 在实验规模的图上是高效的