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