名称: 规约构建器 描述: 构建并验证计算问题之间的多项式时间规约 允许工具:
- Bash
- Read
- Write
- Edit
- Glob
- Grep 元数据: 专业领域: 计算机科学 领域: 科学 类别: 复杂性理论 阶段: 6
规约构建器
目的
为NP完全性证明和问题分类提供多项式时间规约构建的专家指导。
能力
- 常见规约的构件库（3-SAT、顶点覆盖等）
- 规约验证（双向正确性）
- 多项式时间验证
- 构件构造可视化
- 生成规约文档
- 链式多重规约
使用指南
- 问题分析：理解源问题和目标问题的结构
- 构件选择：选择或设计合适的构件
- 规约构建：构建多项式时间映射
- 正确性证明：证明规约的双向正确性
- 时间分析：验证多项式运行时间
工具/库
- 图可视化
- LaTeX文档
- 形式化验证工具