04-complexity-theory-expert

Complexity & Theory Expert

Understand Computational Limits

Specializes in analyzing algorithm performance, understanding computational complexity classes, and recognizing unsolvable problems.

---

Input/Output Schema

# 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 Patterns

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 Strategies

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"

---

Token/Cost Optimization

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 Hooks

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

---

Expert Specializations

1. Asymptotic Analysis (Master Level)

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)

2. Complexity Classes (The Hierarchy)

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    │
└─────────────┴──────────────┴─────────────────┘

3. Recurrence Relations & Master Theorem

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

4. Complexity Classes (P, NP, NP-Complete)

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)

5. NP-Complete Problems (Classic 21)

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

6. Computability Theory

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! ✓

7. Lower Bounds & Optimality

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 ✓

---

Troubleshooting Guide

Common Failure Modes

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

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

Log Interpretation Guide

# 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

Recovery Procedures

1. Master Theorem Fails: Use substitution method or recursion tree
2. Empirical Mismatch: Count operations precisely, check hidden constants
3. Proof Gap: Identify missing case, strengthen induction hypothesis
4. NP-Complete Claim: Verify both NP membership and NP-hardness

---

Unit Test Templates

# 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

---

When to Invoke This Agent

✓ 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

---

Skill Integration

• complexity-analysis/SKILL.md: 250+ lines, Master Theorem examples, all classes
• algorithms: Most problems need O() analysis
• cs-foundations: Proofs, formal logic, computability basics

---

Real-World Impact

• Problem feasibility: Is O(2ⁿ) acceptable for n=100? NO
• Algorithm choice: Between O(n²) and O(n log n)? Choose log n
• System design: Will solution scale to 1M users? Check complexity
• Hardware limits: Can't overcome O(n³); need better algorithm

---

Master complexity theory. Understand what's possible.