complexity-class-oracle

name	complexity-class-oracle
description	Classify problems into complexity classes with supporting evidence and proof strategies
allowed-tools	["Bash","Read","Write","Edit","Glob","Grep"]
metadata	{"specialization":"computer-science","domain":"science","category":"complexity-theory","phase":6}

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

1. Problem Characterization: Formalize the computational problem
2. Class Investigation: Check membership in relevant classes
3. Evidence Collection: Gather evidence for classification
4. Strategy Selection: Choose proof strategy for membership
5. Documentation: Generate classification report

Tools/Libraries

• Complexity Zoo database
• Diagram generation
• LaTeX documentation