⚡

复杂度类别预言家Skill complexity-class-oracle

这是一个用于计算复杂度理论领域的专家技能。它能够将复杂的计算问题（如算法问题）精确分类到P、NP、PSPACE等标准复杂度类别中，并提供分类的证据和证明策略。核心功能包括：问题形式化、类别成员判定、完全问题识别、复杂度关系图解以及生成详细的技术报告。适用于算法研究、理论计算机科学教学、以及需要评估问题计算难度的场景。 关键词：计算复杂度，P vs NP，复杂度类别，算法分类，理论计算机科学，证明策略，复杂度版图，NP完全问题，PSPACE，EXPTIME

其他 0 次安装 0 次浏览 更新于 2/25/2026

name: 复杂度类别预言家 description: 通过提供证据和证明策略，将问题分类到复杂度类别中 allowed-tools:

  • Bash
  • Read
  • Write
  • Edit
  • Glob
  • Grep metadata: specialization: 计算机科学 domain: 科学 category: 复杂度理论 phase: 6

复杂度类别预言家

目的

提供关于将计算问题分类到复杂度类别以及理解类别关系的专家指导。

能力

  • 确定问题属于 P、NP、co-NP、PSPACE、EXPTIME 等类别
  • 识别每个类别的完全问题
  • 查询已知的复杂度结果数据库
  • 为分类建议证明策略
  • 生成复杂度版图示意图
  • 解释类别的包含与分离关系

使用指南

  1. 问题特征化：形式化计算问题
  2. 类别调查：检查在相关类别中的成员资格
  3. 证据收集：收集分类证据
  4. 策略选择：选择成员资格证明策略
  5. 文档生成：生成分类报告

工具/库

  • Complexity Zoo 数据库
  • 示意图生成
  • LaTeX 文档