Abstract
We develop a unified second-order parameterized complexity theory for spaces of integrable functions. This generalizes the well-established case of second-order parameterized complexity theory for spaces of continuous functions. Specifically we prove the mutual linear equivalence of three natural parameterizations of the space $L^p$ of $p$-integrable complex functions on the real unit interval: (binary) $L^p$-modulus, rate of convergence of Fourier series, and rate of approximation by step functions.
Introduction
In classical computational complexity, we measure the efficiency of an algorithm by the number of steps it takes relative to the size of its discrete input. However, when dealing with real-world physical systems—such as those described by the Heat, Wave, or Navier-Stokes equations—the "inputs" are often continuous or integrable functions rather than discrete bitstrings.
Computable analysis provides a framework for this, typically measuring complexity based on the desired output precision (e.g., $n$ bits of accuracy) and a "modulus of continuity" that describes how much the function oscillates. While this works well for continuous functions, it fails for the broader class of $L^p$ spaces (spaces of $p$-integrable functions). Functions in $L^p$ are not necessarily continuous, they are not $\sigma$-compact, and fundamental operations like point evaluation are mathematically undefined. This paper establishes a robust foundation for defining the computational complexity of these essential mathematical objects.
The Problem: Parameterizing Integrable Spaces
To define complexity for a space of functions, one needs a "parameterization"—a way to categorize functions based on their "niceness" or regularity. For continuous functions, the modulus of continuity serves as this parameter. For $L^p$ spaces, the authors identify three natural candidates for such a parameterization:
- $L^p$-modulus ($\mu$): This measures how much a function changes (under the $L^p$ norm) when its input is shifted by a small distance $\delta$. It is the direct $L^p$ analogue of the modulus of continuity, based on the Fréchet–Kolmogorov Theorem.
- Step Rate ($\sigma$): This measures how quickly a function can be approximated by simple step functions (piecewise constant functions).
- Fourier Rate ($\varphi$): This measures the speed at which the function's Fourier series converges to the function itself.
The challenge lies in determining whether these different metrics lead to the same definitions of "polynomial time" or "exponential time." If they did not, the complexity of an $L^p$ function would depend arbitrarily on how the researcher chose to describe it.
Main Result: Linear Equivalence and Robustness
The central contribution of this work is the proof that these three parameterizations are linearly equivalent. Specifically, for any $1 < p < \infty$, the authors prove (Theorem 16) that the Fourier rate, the $L^p$-modulus, and the step rate bound each other linearly. For example, the Fourier rate is bounded by the $L^p$-modulus as $\varphi(n) \le \mu(n + \mathcal{O}(1)) + n + \mathcal{O}(1)$.
From a complexity-theoretic perspective, this implies asymptotic equivalence (Corollary 17). In the same way that changing a discrete algorithm's input from binary to decimal does not change its status as "polynomial time," changing the parameterization of an $L^p$ function between these three metrics does not alter its complexity class.
This robustness is vital for the field. It grants algorithm designers the "freedom of choice": they can use whichever metric is most mathematically convenient for a specific problem—be it spatial shifts, step-approximations, or frequency-domain analysis—with the guarantee that the underlying computational complexity remains consistent.
Methodological Innovations
The proofs leverage classical tools from harmonic analysis and approximation theory, including Minkowski's Integral Inequality, Hölder's inequality, and Fejér kernels. A key distinction in this work is the focus on binary parameterizations.
In many previous formulations, precision was measured in "unary" (e.g., $1/n$). The authors argue that "binary" encoding (measuring error in terms of $2^{-n}$) is superior because it aligns more naturally with classical complexity classes like FP and #P. Binary parameterization avoids artificial exponential blowups in runtime definitions and preserves the logical completeness of the complexity classes.
Furthermore, the authors demonstrate that these equivalences are not limited to one-dimensional functions. They extend the results to $d$-dimensional tori ($\mathbb{T}^d$), provided that Fourier frequencies are handled using the maximum norm to ensure convergence.
Limitations and Future Directions
While the paper provides a solid foundation, it also highlights several open challenges:
- Geometry: The current proofs rely on the simple boundaries of cubes or the "wraparound" nature of tori. Extending these results to complex geometric domains (like triangles or irregular manifolds) remains a significant hurdle.
- Basis Functions: While step functions and Fourier series are equivalent, it remains to be seen which other "natural" Schauder bases induce the same complexity classes.
- Boundary Cases: The equivalence holds for $1 < p < \infty$. The cases of $L^1$ and $L^\infty$ are known to behave differently regarding Fourier convergence and will require specialized treatment.
Conclusion
By unifying the spatial, approximation, and frequency-based views of $L^p$ functions, this paper provides a rigorous and robust framework for the complexity theory of integrable functions. This theoretical groundwork is a necessary step toward a more complete understanding of the computational limits of solving the partial differential equations that govern our physical world.
Summary updated