# Complexity Theory for Operators in Analysis

Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. *ACM Transactions on Computation Theory* **4**(2), Article 5. DOI = 10.1145/2189778.2189780

Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. In *Proceedings of the 42nd ACM Symposium on Theory of Computing* (STOC 2010), pages 495–502, Cambridge, MA, USA. DOI = 10.1145/1806689.1806758

**ArXiv version** (some minor typos have been fixed after the above official version was published)

## Abstract

We propose an extension of the framework
for discussing computational complexity of
problems involving uncountably many objects,
such as real numbers, sets and functions,
that can be represented only through approximation.
The key idea is to use a certain class of string functions,
which we call *regular functions*,
as names representing these objects.
These are more expressive than infinite sequences,
which served as names in prior work that
formulated complexity in more restricted settings.
An important advantage of using regular functions
is that we can define
their *size*
in the way inspired by
higher-type complexity theory.
This enables us to talk about computation on regular functions
whose time or space is bounded polynomially in the input size,
giving rise to more general analogues of the classes
**P**, **NP**, and **PSPACE**.
We also define **NP**- and **PSPACE**-completeness
under suitable many-one reductions.

Because our framework separates machine computation and semantics,
it can be applied to problems on sets of interest in analysis
once we specify a suitable representation (encoding).
As prototype applications,
we consider the complexity of functions (operators) on
real numbers, real sets, and real functions.
The latter two cannot be represented succinctly using
existing approaches based on infinite sequences,
so ours is the first treatment of them.
As an interesting example, the task of numerical algorithms for
solving the initial value problem of differential equations
is naturally viewed as an operator taking real functions to real
functions. As there was no complexity theory for operators,
previous results could only state how complex the solution can be.
We now reformulate them to show that the operator itself
is polynomial-space complete.

- Key words
- computable analysis, computational complexity, higher-type complexity, second-order polynomials