complexity-class-oracle
// Classify problems into complexity classes with supporting evidence and proof strategies
$ git log --oneline --stat
stars:384
forks:73
updated:March 4, 2026
SKILL.mdreadonly
SKILL.md Frontmatter
namecomplexity-class-oracle
descriptionClassify problems into complexity classes with supporting evidence and proof strategies
allowed-toolsBash,Read,Write,Edit,Glob,Grep
metadata[object Object]
Complexity Class Oracle
Purpose
Provides expert guidance on classifying computational problems into complexity classes and understanding class relationships.
Capabilities
- Determine membership in P, NP, co-NP, PSPACE, EXPTIME
- Identify complete problems for each class
- Query known complexity results database
- Suggest proof strategies for classification
- Generate complexity landscape diagrams
- Explain class inclusions and separations
Usage Guidelines
- Problem Characterization: Formalize the computational problem
- Class Investigation: Check membership in relevant classes
- Evidence Collection: Gather evidence for classification
- Strategy Selection: Choose proof strategy for membership
- Documentation: Generate classification report
Tools/Libraries
- Complexity Zoo database
- Diagram generation
- LaTeX documentation