🔢 mathematics

What is a POLYNOMIAL-TIME Computable L2-Function?

This paper proposes two natural definitions for polynomial-time computability of $L^2$ functions and demonstrates that these definitions are incomparable unless the complexity class $FP_1$ includes $\\#P_1$ .

Original authors: Aras Bacho, Svetlana Selivanova, Martin Ziegler

Published 2026-02-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aras Bacho, Svetlana Selivanova, Martin Ziegler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Measuring the "Speed" of Math

Imagine you have a machine that can solve math problems. In computer science, we usually care about how fast this machine works. If the machine solves a problem quickly (specifically, in "polynomial time," which means the time grows reasonably with the size of the input), we call it efficient.

For simple numbers or lists of data, we know exactly how to measure this speed. But what about continuous functions? Think of these as smooth, wavy lines drawn on a graph (like a sound wave or a temperature map). These lines have infinite detail. You can't just "read" the whole line; you have to approximate it.

The paper asks a tricky question: How do we define "fast" when dealing with these infinite, smooth waves?

The authors focus on a specific type of wave called an $L_2$ function. You can think of an $L_2$ function as a "noisy" or "jagged" wave where we don't care about every single tiny point, but rather the average energy of the wave over a period. It's like listening to a song: you care about the overall volume and rhythm, not necessarily the exact air pressure at every single micro-second.

The Problem: Two Ways to Look at a Wave

The authors discovered that there isn't just one way to say a wave is "fast to compute." There are two natural ways to look at it, and they turn out to be incomparable. It's like asking, "Is a car faster than a boat?" The answer depends entirely on whether you are driving on a highway or sailing on a river.

Here are the two definitions they compare:

1. The "Fourier" Approach (The Symphony Conductor)

Imagine you want to describe a complex sound. One way is to break it down into its individual musical notes (frequencies). This is called a Fourier series.

The Definition: A function is "Fourier-computable" if a computer can quickly figure out the volume (coefficient) of each specific musical note needed to build the sound.
The Catch: The computer must be able to calculate the volume of any note, even very high-pitched ones, very quickly.

2. The "Step" Approach (The Pixelated Image)

Imagine you want to describe a picture. One way is to break it into a grid of small squares (pixels) and assign an average color to each square. This is a step function.

The Definition: A function is "Step-computable" if a computer can quickly figure out the average height of the wave within specific, small time blocks.
The Catch: The computer must be able to calculate the average height for every single block quickly.

The Big Discovery: They Don't Match!

The paper's main finding is surprising: Just because you can quickly calculate the musical notes (Fourier), doesn't mean you can quickly calculate the pixel averages (Step), and vice versa.

Scenario A: You can have a wave where the computer knows the notes perfectly fast, but if you try to calculate the average height of a specific tiny block, the computer gets stuck and takes forever.
Scenario B: You can have a wave where the computer can quickly calculate the average height of every block, but if you try to figure out the specific volume of a single high-pitched note, the computer gets stuck.

The authors prove that these two definitions are incomparable. Unless a major unsolved mystery in computer science is solved (specifically, unless a class of hard counting problems called #P turns out to be easy, which most experts doubt), one definition does not imply the other.

The "Average" Compromise

The authors also introduce a third, slightly softer definition called "Step-computable in mean."

Instead of demanding the computer be fast at every single block (worst-case), they only demand it be fast on average.
It's like a student taking a test: The "worst-case" definition says they must get every single question right instantly. The "average" definition says they can take a little longer on a few hard questions, as long as their overall speed is still fast.

They found that this "average" version actually matches the "Fourier" version perfectly. If you can calculate the notes fast, you can calculate the average block heights fast, and vice versa.

Why Does This Matter? (The Heat Equation)

The paper ends with a practical example: The Heat Equation. This is a famous math formula that describes how heat spreads out over time (like a hot pan cooling down).

The Old View: In previous studies, if you started with a "fast" (polynomial-time) heat pattern, the result after some time might become "slow" and uncomputable.
The New View: Using the authors' new "Fourier" definition, they show that if you start with a "fast" heat pattern, the result remains "fast."

This suggests that the way we define "fast" changes the outcome of the math. If you use the "Step" definition, the heat equation might break down; if you use the "Fourier" definition, it works smoothly.

Summary Analogy

Imagine you are trying to describe a mountain range to a friend.

Fourier Method: You describe the mountain by listing the height of every specific peak and valley (the frequencies).
Step Method: You describe the mountain by dividing it into a grid of 1-mile squares and telling your friend the average elevation of each square.

The paper says:

You might be able to list all the peaks quickly (Fourier), but calculating the average elevation of a specific 1-mile square might take you years (Step).
Or, you might be able to give the average elevation of every square quickly (Step), but figuring out the exact height of a specific tiny peak might take you years (Fourier).
However, if you are okay with giving the average elevation of the squares generally (ignoring the occasional slow square), then you are just as good as the person listing the peaks.

The authors are essentially saying: "We need to be very careful about which definition of 'fast' we use, because they lead to different mathematical realities."

Technical Summary: What is a Polynomial-Time Computable L2-Function?

Problem Statement
The paper addresses the foundational challenge of defining "polynomial-time computability" for functions in the space $L^2[0; 1]$ (complex-valued, square-integrable functions). While computability and complexity for continuous functions ( $C[0; 1]$ ) are well-established via pointwise approximation and modulus of continuity, these definitions do not directly translate to $L^2$ functions. $L^2$ functions are equivalence classes defined up to sets of measure zero, rendering pointwise evaluation $x \mapsto f(x)$ algorithmically ill-defined. The authors seek natural, quantitative definitions for $L^2$ computability that align with classical complexity theory (specifically polynomial time and $\#P$ ) and investigate whether these definitions are equivalent or distinct.

Methodology
The authors propose and analyze three distinct definitions of polynomial-time computability for $f \in L^2[0; 1]$ , based on different dense subsets of the space:

Fourier-Computability (Definition 2a): $f$ is computable if its Fourier coefficients can be approximated by Gaussian dyadic rationals in polynomial time, and the partial sums of the Fourier series converge to $f$ in the $L^2$ -norm at a specific rate (exponential-polynomial).
Step-Computability (Definition 2b): $f$ is computable if it can be approximated by piecewise constant functions (step functions) with equidistant steps, where the height of every step is computable in polynomial time (worst-case complexity).
Step-Computability in Mean (Definition 2c): A relaxation of (b) where the approximation requirement is shifted to the average-case. The $L^2$ -error of the step approximation must be small, but individual step heights need not be computable in worst-case polynomial time; rather, the average error over the steps must be bounded efficiently.

The authors utilize techniques from Computable Analysis and Complexity Theory, specifically:

GapP and $\#P$ : They define versions of these notions where the coefficients belong to the class GapP (closure of $\#P$ under subtraction), allowing for a finer analysis of counting problems embedded in continuous functions.
Encoding Discrete Problems: To prove separations between these notions, the authors encode discrete $\#P_1$ -complete problems (counting witnesses for unary inputs) into the coefficients of $L^2$ functions. They employ "well-separation" techniques (using ternary encoding or specific weight decay) to ensure that recovering the discrete count from the continuous function's approximation is possible only if the underlying complexity classes collapse (e.g., $\#P_1 \subseteq FP_1$ ).
Parseval's Isometry: They leverage the isometry between $L^2$ and $\ell^2$ to relate Fourier coefficients to step-function approximations.

Key Contributions and Results

Incomparability of Definitions: The central result is that the proposed definitions are incomparable unless $\#P_1 \subseteq FP_1$ .
- Theorem 5: There exists a function that is Fourier-computable in polynomial time but is not Step-computable in polynomial time (in the worst-case sense). Recovering the value of a specific step from such a function would solve a $\#P_1$ -complete problem.
- Theorem 6: Conversely, there exists a function that is Step-computable in polynomial time in mean but is not Fourier-computable in polynomial time. Specifically, the zeroth Fourier coefficient (the integral) of such a function encodes a $\#P_1$ -complete problem, making it hard to compute in the Fourier sense, even though the function is easy to approximate on average via steps.
Equivalence under $\#P$ :
- Theorem 4: If one relaxes the complexity constraint from polynomial time to $\#P$ (specifically, allowing coefficients to be in GapP), then Fourier-computability in $\#P$ is equivalent to Step-computability in $\#P$ in mean. This suggests that the gap between the definitions is purely a matter of worst-case vs. average-case complexity within the counting hierarchy.
Relationship to Continuous Functions ( $C[0; 1]$ ):
- Theorem 7 & 8: For continuous functions with a polynomial modulus of continuity, standard polynomial-time computability implies both Fourier and Step computability in $\#P$ . However, the converse is not always true without the modulus of continuity.
- Theorem 10: Even for smooth ( $C^\infty$ ) functions, being Fourier-computable in polynomial time does not guarantee that pointwise values (e.g., $f(0)$ ) are polynomial-time computable, unless $\#P_1 \subseteq FP_1$ . This highlights a fundamental divergence between $L^2$ -based definitions and pointwise evaluation.
Application to the Heat Equation:
- Theorem 13: The authors apply their framework to the heat equation $u_t = u_{xx}$ . They show that if the initial condition $f \in L^2[0; 1]$ is Fourier-computable in polynomial time, then the solution $u(\cdot, t)$ at any polynomial-time computable time $t > 0$ remains Fourier-computable in polynomial time.
- Contrast: This stands in contrast to classical results (Remark 14) where a polynomial-time computable initial condition (in the $C[0; 1]$ sense) can lead to a solution that is not polynomial-time computable as a continuous function. The new $L^2$ -Fourier definition preserves tractability for the heat equation.

Significance
The paper argues that there is no single, canonical definition of polynomial-time computability for $L^2$ functions. The choice between Fourier-based and Step-based definitions leads to different complexity classes. The authors demonstrate that:

Worst-case vs. Average-case: The distinction between "Step-computable" and "Step-computable in mean" is crucial; the latter aligns with Fourier-computability under $\#P$ , while the former is strictly stronger and potentially intractable for certain functions.
Complexity Blow-up: The paper confirms that moving from continuous to integrable functions introduces complexity blow-ups similar to those found in other functional operators, but the nature of this blow-up depends heavily on the chosen representation (Fourier vs. Step).
Foundational Clarity: By establishing these separations, the paper provides necessary caution for researchers defining complexity classes for PDEs and integrable functions, suggesting that "polynomial-time computable $L^2$ function" must be qualified by the specific representation (Fourier or Step) and the complexity class (P or $\#P$ ) being used.

The work concludes that while the definitions are distinct, they offer a nuanced landscape where average-case complexity (Step in mean) recovers the equivalence with Fourier methods, provided one operates within the $\#P$ framework.