Human-Agent Computation Systems: A Complexity-Theoretic Sketch

Definition: Human-Agent Computation System (HACS)

A HACS is a tuple \((A, H, W, \Sigma, \delta)\) where:

• \(A\) = Agent
  • Input: bounded context window \(c \in \Sigma^{\leq k}\) (for fixed \(k\))
  • Output: action \(a \in \mathcal{A}\) (write to workspace, query human, halt)
• \(H\) = Human oracle
  • Function \(H: \Sigma^* \rightarrow \Sigma^*\) (possibly partial, possibly stochastic)
  • Latency \(\tau_H\) per invocation
• \(W\) = Workspace (unbounded tape)
  • \(W \in \Sigma^*\)
• \(\delta\) = Context formation function
  • \(\delta: W \times \text{History} \rightarrow \Sigma^{\leq k}\) (what the agent “sees”)

One computational step:

1. Form context: c = δ(W, history)
2. Compute action: a = A(c)         [time: τ_A]
3. Execute action:
   - If a = write(σ, pos): W[pos] := σ
   - If a = query(q): receive H(q)  [time: τ_H]
   - If a = halt(output): terminate
4. Append to history
5. Goto 1

I feel this is now precise enough to ask complexity questions about.

The Fundamental Difference from Classical Turing Machines (TMs)

In classical complexity theory, we count steps and treat them as unit cost.

In HACS:

This creates a natural cost hierarchy: \(\tau_R < \tau_W \ll \tau_A \ll \tau_H\)

Implication 1: Human Queries Are Precious

If we’re minimizing wall-clock time, we want to minimize \(\sum_i 1\times[\text{step } i \text{ queries human}]\)

This connects to query complexity in computational learning theory:

• How many queries to an oracle are needed to solve a problem?
• PAC learning bounds, membership query complexity

Concrete result that transfers: In many learning settings, there are lower bounds of \(\Omega(\log n)\) or \(\Omega(n)\) queries. This suggests some tasks fundamentally require multiple human interactions; you can’t engineer around it.

Implication 2: Amortization Becomes Critical

If \(\tau_A\) is significant (seconds per step), then a task requiring \(n\) serial steps takes at least \(n \cdot \tau_A\) time.

But: The agent can sometimes do \(O(1)\) steps that accomplish \(O(n)\) “logical operations” (e.g., asking the workspace to run a compiler, database query, or external computation).

This is analogous to:

• Word RAM model vs unit-cost RAM (one operation can process \(w\) bits)
• PRAM (parallel computation within a step)
• Circuit complexity (depth vs. size tradeoffs)

The agent’s “step count” is like “circuit depth”, while the work done per step is like “circuit width”.

Implication 3: Parallelism Within Bounded Depth

Some agent architectures allow parallel tool calls within one step. If we can execute \(p\) parallel operations:

\(T_{\text{parallel}}(n) = \frac{T_{\text{sequential}}(n)}{p} + \text{coordination overhead}\)

This connects to NC complexity (Nick’s Class) problems solvable in polylogarithmic depth with polynomial processors.

Question: Are there tasks that are “in P” (polynomial steps) but not “in NC” for HACS? I.e., tasks that fundamentally resist parallelization even with unlimited tool parallelism?

Plausibly yes: tasks with sequential dependencies in reasoning (each step requires the output of the previous) seem analogous to P-complete problems like Circuit Value Problem.

The Two-Level Memory Model

┌─────────────────────────────────────────────┐
│           CONTEXT WINDOW (size k)           │
│         ┌───────────────────────┐           │
│         │ "Fast" memory         │           │
│         │ O(1) access time      │           │
│         │ Bounded: |c| ≤ k      │           │
│         └───────────────────────┘           │
│                    ↑↓ δ (context formation) │
│         ┌───────────────────────┐           │
│         │ WORKSPACE             │           │
│         │ "Slow" memory         │           │
│         │ O(?) access time      │           │
│         │ Unbounded             │           │
│         └───────────────────────┘           │
└─────────────────────────────────────────────┘

This is analogous to the External Memory Model (Aggarwal & Vitter, 1988):

• Fast memory of size \(M\) (context window, size \(k\))
• Slow memory of unbounded size (workspace)
• Block transfers of size \(B\) (how much we can read/write per step)

Key Results That Transfer

Classical Halting Problem

For TMs: Given \((M, x)\), does \(M\) halt on \(x\)? Undecidable.

Variations on the theme of undecidability

• Level 1: The agent’s code execution - When the agent runs code in the workspace, determining if that code halts is undecidable. The agent cannot reliably know if subprocess.run(user_code) will finish.
• Level 2: The agent’s own behavior - Given a task description \(T\) and initial workspace \(W_0\), does the agent-loop halt? Also undecidable, by reduction from the standard halting problem.
• Level 3: The human-included system - Does the full HACS halt on task \(T\)? This depends on \(H\) (the human), which is:
  • Not even computable in the formal sense
  • Subject to external factors (human gets bored, dies, changes mind)

These points make it interesting to ask: “can we ever make an AI agent sufficiently clever that it can work on a specification and that we can always expect it to finish the task on its own?” If the answer is “no” (likely), what will be the shape of the boundary between what is doable and what isn’t?

Rice’s Theorem Applies

Rice’s Theorem: Any non-trivial semantic property of programs is undecidable.

HACS interpretation: The agent cannot reliably determine:

• “Will this code change do what the user wants?” (semantic)
• “Is this codebase bug-free?” (semantic)
• “Does this refactoring preserve behavior?” (semantic)

This is a limitation of computation itself, not just the limits of current LLMs.

What the Human Oracle Buys Us

If \(H\) is an oracle for the halting problem (i.e., human can always correctly judge “is this done?”), then HACS can compute functions in \(0'\) (Turing jump of the computable functions).

But humans aren’t halting oracles. We’re more like:

• Bounded oracles: Can only answer queries up to some complexity
• Noisy oracles: Sometimes wrong
• Strategic oracles: May have different objectives than the agent

This suggests modeling with:

• Approximate oracle machines (studied in computability theory)
• Interactive proofs with bounded provers

Context: the IP = PSPACE Theorem

Setup:

• Prover (unbounded computation)
• Verifier (polynomial time, randomized)
• Multi-round interaction

Result: Any language in PSPACE can be verified through interaction.

HACS as Interactive Proof

Consider the agent as prover, human as verifier:

Something we already had an intuition about: the human doesn’t need to understand how the agent solved the problem, they only need to verify the solution. Verification can be easier than solving.

What HACS Can “Prove” to Humans

For which task classes can the agent convince a bounded human that the work is correct?

Easy to verify:

• Code that passes tests (human runs tests)
• Proofs in formal systems (human checks with proof assistant)
• Factual claims (human can spot-check)

Hard to verify:

• “This is the best solution” (optimization without certificate)
• “This code has no bugs” (requires exhaustive reasoning)
• “This is creative” (subjective, no formal criterion)

The verification asymmetry explains a lot about where agents succeed and fail.

A Question

How many bits must be exchanged between agent and human to solve task \(T\)?

Lower Bounds Mean Fundamental Limits

Classic result (Set Disjointness): Determining if Alice’s set and Bob’s set are disjoint requires \(\Omega(n)\) bits of communication.

HACS interpretation: If a task requires the human to convey \(n\) bits of implicit requirements, there’s no way around substantial interaction. “Just understand what I want” has information-theoretic limits.

Implications for Agent Design

1. Specification complexity - If a task has Kolmogorov complexity \(K(T) = n\), the human must somehow convey those \(n\) bits. You can’t compress the requirements below their intrinsic complexity.
2. Iterative refinement is sometimes optimal - Rather than one long specification, iterative refinement might be communication-optimal for tasks where the human can evaluate intermediate outputs. This is like binary search over the space of intended outputs.
3. Shared context reduces communication - If agent and human share a “prior” (common knowledge, conventions), the communication needed drops. This is why domain-specific agents can be more efficient: they share more prior with expert users. Conversely, trying to orient users towards more “general-purpose” LLMs may increase the communication costs to get anything done.