A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For example (a more formal treatment is below), a computation in $\mathrm{Time}(n^2)(\mathrm{TimeSpace}(n^4,n)+\mathrm{TimeSpace}(n^3, n^2))$ will run two independent computations, one with time $n^4$ and space $n$ and another with time $n^3$ and space $n^2$, and then have time $n^2$ to combine the results. A computation in $(m⋅\mathrm{TimeSpace}(\log n,\log n,1))^p$ represents $p$ steps on a machine with $m$ 1bit cells, with each cell update (each cell is updated every step) computable in $\mathrm{TimeSpace}(\log n, \log n)$. In turn, these computations can be combined into bigger ones.
Question: Have similar constructions of complexity classes been studied in literature? If yes, references and other notes will be interesting.
Formally, we will denote complexity classes (sets of functions) by expressions as follows.
$x$ is the problem instance; $n=|x|$. An intermediate computation result will be denoted by $y$. A component using $y$ can access $n$ but (unless otherwise noted) not $x$; note that we can have |y|<|x|. For simplicity, for each component, the output length depends only on $n$ and is easily computable.
The basic ingredient is $\mathrm{TimeSpace}$: $g$ is in $\mathrm{TimeSpace}(T,S,L)$ iff $g$ is computable on RAM machines in time $T$ and space $S$ bits, outputting $L$ bits. Here, $g$ is a function (using $y$ and $n$ as (read-only) input) with easily computable output length: $|g(y)| = h(n) ∈ \mathrm{TimeSpace}(\mathrm{polylog}(n+h(n))|), O(\log(n+h(n)))$. To make the length condition nonrestrictive, and to make the class independent of whether we use log-cost RAM, reasonable unit-cost RAM, TM on binary trees, etc, we require that:
$L≤S≤T$, $L≡O(L)$, $S≡O(S + \log(n+|y|))$, $T≡T \, \mathrm{polylog}(n+|y|)$; $∀(\text{computable } f ∈ L) \, ∃(h∈L \text{ as above}) \, h > f$.
$L,S,T$ depend only on $n$, and the above properties impose a limit on $|y|$ above which we are not defining $\mathrm{TimeSpace(T,S,L)}$. Also, $\mathrm{TimeSpace}(T,S) ≡ \mathrm{TimeSpace}(T,S,S)$.
Combining functions
Composition: A function in $FG$ with input $y$ returns $f(g(y))$ for some $f∈F$ and $g∈G$ ($f$ and $g$ are independent of $n$ and $y$ but may use $n$ as an implicit argument; the same applies below).
Iteration: A function in $F^{h(n)}$ with input $y$ returns the result of iterating $f$ $h(n)$ times for some $f∈F$, with input $y$ (and first iteration marker) given to the first iteration (numeric function $h$ is in $\mathrm{TimeSpace}(\mathrm{polylog}(n+h(n)), O(\log(n+h(n))))$; as defined, this operation is nonmonotonic in $h$ (and nonstandard) if $F$ implies $o(\log h(n))$ output size).
Addition (parallel): A function in $F+G$ with input $y$ returns the concatenation of $f(y)$ and $g(y)$ for some $f∈F$ and $g∈G$ (note that all lengths are effectively known).
Multiplication by a numeric function: A function in $h(n)⋅F$ with input $y$ returns $f(y,0)+f(y,1)+...+f(y,h(n)-1)$ for some $f∈F$ (using a reasonable coding for pairs; '+' is concatenation here).
Constants and input: A function in $x$ with input $y$ returns $x$ (the problem instance; we use symbol $x$ both for the problem instance and for the set of functions returning it). As a complexity class, $F$ is identified with $F(x)$.
An extension for nondeterminism
min: A function in $\min_{h(n)} F$ with input $y$ returns $\min(f(y,i): i < h(n))$ for some $f∈F$ ($i$ is a natural number).
search: A multivalued function in $\mathrm{search}_{h(n)}(F)$ with input $y$ returns some nonzero $f(y,i)$ (or 0 if there is no such $i < h(n)$) for some $f∈F$. A multivalued function solves a problem iff all of its possible values are valid; the above definitions work for multivalued functions.
decision (batch): A function in $\mathrm{union}_{h(n)} F$ with input $y$ returns the bitwise 'or' of $(f(y,i): i < h(n))$ for some $f∈F$.
Provable relations (for appropriate parameters)
- All operations are monotonic in all arguments, where monotonicity and equivalence ('≤' and '=' below) are under $\mathrm{TimeSpace}(\mathrm{polylog},\log)$ reducibility for output bits.
- Addition is commutative and associative and agrees with multiplication; multiplication is associative (and distributive over addition); composition is associative; power agrees with composition.
- $FF = F+F = F$ (assuming $F$ is built up using TimeSpace,+,⋅,composition,power,$x$)
- $m⋅\mathrm{TimeSpace}(T,S,L) ≤ \mathrm{TimeSpace}(mT,\max(S,mL),mL)$
- $\mathrm{TimeSpace}(T,S,L)^p ≤ \mathrm{TimeSpace}(pT,S,L)$, with equality if $L=S$ (and reverse inclusion if we somehow permitted $L>S$)
- $y ≤ (m⋅\mathrm{TimeSpace}(T,S,L))(y)$ if $|y|≤mL$
- $\small{\mathrm{TimeSpace}(T_1,S_1,L_1) (m⋅\mathrm{TimeSpace}(T_2,S_2,L_2)) ≤ \mathrm{TimeSpace}(T_1 T_2,S_1+S_2,L_1)}$
An interesting additional question would be to find the full set of true relations in (TimeSpace,+,⋅,composition,power,≤) where all numeric values are of the form $\tilde{O}(n^c)$ (positive rational constant $c$), assuming that the complexity classes are as incomparable as it appears possible.
