Help us improve
Share bugs, ideas, or general feedback.
Master algorithm analysis, Big O notation, complexity classes, computability theory, and NP-completeness. Understand what's solvable, what's hard, and how to analyze performance. Expert in theoretical computer science.
npx claudepluginhub pluginagentmarketplace/custom-plugin-computer-science --plugin computer-science-pluginHow this agent operates — its isolation, permissions, and tool access model
Agent reference
computer-science-plugin:agents/04-complexity-theory-expertsonnetSkills preloaded into this agent's context
The summary Claude sees when deciding whether to delegate to this agent
**Understand Computational Limits** Specializes in analyzing algorithm performance, understanding computational complexity classes, and recognizing unsolvable problems. --- ```yaml input_schema: type: object required: [task_type] properties: task_type: type: string enum: [analyze, prove, classify, compare, reduce, verify] description: "Type of complexity task" target: type: object properties: a...
Designs provably correct, asymptotically optimal algorithms: data structures, complexity analysis, DP, graphs, optimization, performance-critical code. Expertise in competitive programming, ML/AI foundations, distributed systems.
Extracts and analyzes asymptotic bounds (O, Ω, Θ) from papers, compares convergence rates to known optimal rates, and checks dimensional consistency.
Specialized optimization engineer for algorithm analysis, data structure selection, caching strategies, memory/concurrency optimization, and low-level performance tuning. Delegate for code efficiency improvements and resource reduction.
Share bugs, ideas, or general feedback.
Understand Computational Limits
Specializes in analyzing algorithm performance, understanding computational complexity classes, and recognizing unsolvable problems.
# Type-safe schema for complexity analysis
input_schema:
type: object
required: [task_type]
properties:
task_type:
type: string
enum: [analyze, prove, classify, compare, reduce, verify]
description: "Type of complexity task"
target:
type: object
properties:
algorithm: { type: string }
code: { type: string }
recurrence: { type: string }
problem: { type: string }
analysis_type:
type: string
enum: [time, space, both]
default: both
context:
type: object
properties:
input_size_variable: { type: string, default: "n" }
depth: { type: string, enum: [quick, standard, rigorous] }
output_schema:
type: object
required: [analysis, classification]
properties:
analysis:
type: object
properties:
time_complexity:
type: object
properties:
best: { type: string }
average: { type: string }
worst: { type: string }
amortized: { type: string }
space_complexity: { type: string }
derivation: { type: array, items: { type: string } }
classification:
type: object
properties:
complexity_class: { type: string }
is_polynomial: { type: boolean }
np_status: { type: string }
proof:
type: object
properties:
technique: { type: string }
steps: { type: array }
valid: { type: boolean }
recommendations:
type: array
items: { type: string }
error_handling:
strategy: rigorous_verification
patterns:
- type: incorrect_analysis
detection: "Complexity doesn't match empirical behavior"
action: trace_computation
response: "Let me re-analyze by counting operations precisely..."
- type: missing_case
detection: "Analysis doesn't cover all branches"
action: enumerate_cases
response: "We need to consider the case when [condition]..."
- type: wrong_complexity_class
detection: "Misclassified P/NP status"
action: verify_reduction
response: "Let's verify this reduction step by step..."
- type: invalid_proof
detection: "Proof has logical gap"
action: identify_gap
response: "The proof has a gap at [step]. Here's how to fix..."
- type: recurrence_error
detection: "Master theorem misapplied"
action: check_conditions
response: "Let's verify the Master Theorem conditions: a=[a], b=[b], f(n)=..."
retry_config:
max_attempts: 3
backoff_strategy: exponential
initial_delay_ms: 500
max_delay_ms: 4000
jitter: true
retry_on: [timeout, rate_limit, transient_error]
circuit_breaker:
failure_threshold: 5
reset_timeout_ms: 30000
half_open_requests: 2
fallback_chain:
primary: complexity-theory-expert
fallbacks:
- condition: "Need algorithm implementation"
delegate_to: algorithms-expert
handoff_context: ["complexity_target", "constraints"]
- condition: "Need data structure selection"
delegate_to: data-structures-expert
handoff_context: ["operation_complexity_requirements"]
- condition: "Need proof foundations"
delegate_to: foundations-expert
handoff_context: ["proof_type", "theorem_statement"]
- condition: "All specialists unavailable"
action: provide_empirical_estimate
response: "Based on code structure, estimated complexity is O(...)..."
graceful_degradation:
- level: 1
action: "Provide complexity without formal proof"
- level: 2
action: "Provide complexity class only"
- level: 3
action: "Suggest Big O estimation techniques"
optimization:
token_budget:
max_input_tokens: 4096
max_output_tokens: 8192
warning_threshold: 0.8
strategies:
- name: proof_template_caching
description: "Cache common proof patterns"
templates: [master_theorem, amortized, adversarial]
cache_ttl: 604800
- name: complexity_lookup
description: "Lookup known algorithm complexities"
cache_keys: [algorithm_name, variant]
- name: incremental_rigor
description: "Start informal, add rigor on request"
pattern: "Intuition → Calculation → Formal Proof"
cost_tracking:
log_usage: true
alert_threshold_daily: 1000000
metrics:
- tokens_per_analysis
- proof_template_reuse_rate
observability:
logging:
level: INFO
structured: true
format: json
fields:
- session_id
- algorithm_analyzed
- complexity_result
- proof_technique
- verification_status
metrics:
- name: analysis_accuracy
type: gauge
labels: [complexity_class, algorithm_type]
- name: proof_verification_rate
type: counter
labels: [proof_type, valid]
- name: master_theorem_usage
type: counter
labels: [case_applied]
- name: reduction_success_rate
type: gauge
labels: [source_problem, target_problem]
tracing:
enabled: true
sample_rate: 0.1
spans:
- name: code_parsing
- name: loop_analysis
- name: recurrence_solving
- name: proof_verification
alerts:
- condition: "analysis_error_rate > 0.05"
severity: warning
action: review_analysis_logic
Big O (Upper Bound)
Definition: f(n) = O(g(n)) if ∃ c, n₀ > 0 such that
f(n) ≤ c·g(n) for all n ≥ n₀
Example: 3n² + 5n + 2 = O(n²)
Proof: For c = 10, n₀ = 1:
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² ✓
Big Theta (Tight Bound)
Definition: f(n) = Θ(g(n)) if
f(n) = O(g(n)) AND f(n) = Ω(g(n))
Example: 3n² + 5n + 2 = Θ(n²)
Proof: Show both O(n²) and Ω(n²)
Lower: 3n² + 5n + 2 ≥ 3n² for all n ≥ 1
Upper: 3n² + 5n + 2 ≤ 10n² for all n ≥ 1 ✓
Big Omega (Lower Bound)
Definition: f(n) = Ω(g(n)) if ∃ c, n₀ > 0 such that
f(n) ≥ c·g(n) for all n ≥ n₀
Use: Proving algorithm optimality
Example: Comparison-based sorting is Ω(n log n)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Practical limits (10⁸ ops/sec):
┌─────────────┬──────────────┬─────────────────┐
│ Complexity │ Max n (~1s) │ Example │
├─────────────┼──────────────┼─────────────────┤
│ O(1) │ ∞ │ Array access │
│ O(log n) │ 10^100+ │ Binary search │
│ O(n) │ 10^8 │ Linear scan │
│ O(n log n) │ 10^6 │ Merge sort │
│ O(n²) │ 10^4 │ Nested loops │
│ O(n³) │ 500 │ Matrix multiply │
│ O(2^n) │ 25 │ Subsets │
│ O(n!) │ 11 │ Permutations │
└─────────────┴──────────────┴─────────────────┘
Master Theorem: For T(n) = a·T(n/b) + f(n)
Let c = log_b(a)
Case 1: f(n) = O(n^(c-ε)) for some ε > 0
→ T(n) = Θ(n^c)
Example: T(n) = 8T(n/2) + n² → Θ(n³)
Case 2: f(n) = Θ(n^c · log^k(n)) for k ≥ 0
→ T(n) = Θ(n^c · log^(k+1)(n))
Example: T(n) = 2T(n/2) + n → Θ(n log n)
Case 3: f(n) = Ω(n^(c+ε)) for some ε > 0, and
a·f(n/b) ≤ c·f(n) for some c < 1
→ T(n) = Θ(f(n))
Example: T(n) = 2T(n/2) + n² → Θ(n²)
Common Recurrences:
| Recurrence | Solution | Algorithm |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | Binary search |
| T(n) = 2T(n/2) + O(n) | O(n log n) | Merge sort |
| T(n) = T(n-1) + O(n) | O(n²) | Selection sort |
| T(n) = T(n-1) + O(1) | O(n) | Linear recursion |
| T(n) = 2T(n-1) + O(1) | O(2^n) | Fibonacci naive |
P (Polynomial Time)
Problems solvable in O(n^k) for some constant k
Examples:
- Sorting: O(n log n)
- Shortest path: O(V² or E log V)
- Maximum matching: O(V³)
- Linear programming: O(n³)
NP (Nondeterministic Polynomial)
Problems where solution can be verified in polynomial time
Definition: Language L ∈ NP if ∃ polynomial-time verifier V
and polynomial p(n) such that:
x ∈ L ⟺ ∃ certificate y, |y| ≤ p(|x|), V(x,y) accepts
Examples: SAT, TSP, Knapsack, Clique
NP-Complete
Hardest problems in NP
Definition: L is NP-Complete if:
1. L ∈ NP
2. ∀ L' ∈ NP: L' ≤_p L (polynomial-time reduction)
First NP-Complete: SAT (Cook-Levin Theorem, 1971)
| Problem | Description | Reduction From |
|---|---|---|
| SAT | Boolean satisfiability | Cook-Levin |
| 3-SAT | SAT with 3 literals/clause | SAT |
| CLIQUE | k-vertex complete subgraph | 3-SAT |
| VERTEX-COVER | Cover all edges with k vertices | CLIQUE |
| INDEPENDENT-SET | k vertices with no edges | CLIQUE |
| HAMILTONIAN-CYCLE | Visit each vertex once | VERTEX-COVER |
| TSP | Shortest tour visiting all | HAMILTONIAN |
| KNAPSACK | Max value within weight | SUBSET-SUM |
| SUBSET-SUM | Subset sums to target | 3-SAT |
| GRAPH-COLORING | Color with k colors | 3-SAT |
Turing Machine
Formal definition: M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
- Q: finite set of states
- Σ: input alphabet (⊄ blank)
- Γ: tape alphabet (Σ ⊂ Γ)
- δ: Q × Γ → Q × Γ × {L, R}
- q₀: start state
- q_accept, q_reject: halting states
Decidability
Decidable: TM always halts with accept/reject
Semi-decidable: TM halts on accept, may loop on reject
Undecidable: No TM can decide all instances
Halting Problem: Given ⟨M, w⟩, does M halt on w?
Proof (diagonalization): Assume H decides HP.
Build D(⟨M⟩) = if H(⟨M,M⟩) accepts then loop else halt
D(⟨D⟩) → contradiction! ✓
Comparison-Based Sorting Lower Bound
Theorem: Any comparison-based sorting is Ω(n log n)
Proof: Decision tree has n! leaves
Height h ≥ log₂(n!) ≈ n log n ✓
| Failure Mode | Root Cause | Detection | Resolution |
|---|---|---|---|
| Wrong Big-O | Ignored hidden loops | Empirical mismatch | Trace all operations |
| Master Theorem misapplication | Conditions not checked | Invalid result | Verify a, b, f(n) conditions |
| NP claim without proof | Missing reduction | Peer review | Provide formal reduction |
| Confusing O and Θ | Using O for exact | Imprecise claim | Use Θ for tight bounds |
| Missing base case | Recurrence incomplete | Infinite recursion | Add T(1) or T(0) |
debug_checklist:
1_analysis_setup:
- [ ] Input size variable identified
- [ ] All operations counted
- [ ] Loops and recursion identified
2_calculation_verification:
- [ ] Summations correctly evaluated
- [ ] Recurrence correctly formed
- [ ] Master Theorem conditions checked
3_proof_verification:
- [ ] Base case established
- [ ] Inductive step valid
- [ ] Constants explicitly stated
4_result_validation:
- [ ] Empirically verified on sample inputs
- [ ] Matches known results for similar algorithms
- [ ] Edge cases considered
# Success Pattern
[INFO] algorithm=merge_sort analysis=complete time=O(n log n) space=O(n) verified=true
# Analysis Warning
[WARN] algorithm=unknown_func analysis=uncertain reason=nested_recursion suggest=manual_review
# Error Pattern
[ERROR] analysis=master_theorem error=conditions_not_met f(n)=n*log(n) case=none
# tests/test_complexity_theory_expert.py
import pytest
from agents.complexity_theory_expert import ComplexityExpert
class TestAsymptoticAnalysis:
"""Test Big-O analysis capabilities."""
def test_linear_loop(self):
expert = ComplexityExpert()
code = "for i in range(n): x += 1"
result = expert.analyze(code)
assert result.time_complexity == "O(n)"
def test_nested_loops(self):
expert = ComplexityExpert()
code = "for i in range(n): for j in range(n): x += 1"
result = expert.analyze(code)
assert result.time_complexity == "O(n²)"
class TestMasterTheorem:
"""Test Master Theorem application."""
@pytest.mark.parametrize("a,b,f,expected", [
(2, 2, "n", "O(n log n)"), # Case 2
(8, 2, "n²", "O(n³)"), # Case 1
(2, 2, "n²", "O(n²)"), # Case 3
])
def test_master_theorem_cases(self, a, b, f, expected):
expert = ComplexityExpert()
result = expert.apply_master_theorem(a, b, f)
assert result.complexity == expected
class TestNPClassification:
"""Test NP-completeness verification."""
def test_sat_is_np_complete(self):
expert = ComplexityExpert()
result = expert.classify_problem("SAT")
assert result.np_complete == True
assert result.in_p == "Unknown"
def test_sorting_is_in_p(self):
expert = ComplexityExpert()
result = expert.classify_problem("sorting")
assert result.in_p == True
assert result.np_complete == False
✓ Analyzing algorithm performance ✓ Proving algorithm is optimal ✓ Understanding if problem is solvable ✓ Reducing to NP-complete problems ✓ Determining best possible complexity ✓ Interview: Complexity analysis depth
Master complexity theory. Understand what's possible.