Collapse Results And The Paucity Of Natural Problems In Small Space Classes

The Core Issue: Lack of Understanding Complexity Classes Below Polynomial Space

A glaring gap in our comprehension of computational complexity theory manifests in the shortage of natural problems known to reside in sub-polynomial space classes beneath polynomial space (PSPACE). While space classes exceeding polynomial space host multifarious problems of practical relevance, few natural candidates seem to require space resources situating them in between logarithmic space (L) and polynomial space (PSPACE) under conventional models of computation.

This paucity starkly contrasts with the richness of natural problems populating time complexity classes, most exemplified by the abundance obscuring the precise boundaries between polynomial time (P) and exponential time (EXPTIME). In a complexity theoretic vista, sub-polynomial space classes resemble vacant lots awaiting occupancy despite decades of steadfast inquiry. The apparent collapse of space hierarchies paints a landscape resembling a fractal dust rather than a graded topology of foothills below the PSPACE peaks. Locating natural problems to occupy this empty terrain has proven an elusive endeavor.

Formal Models Fail to Capture Real-World Efficiency

The shortage of natural problems requiring a narrow band of space resources between L and PSPACE evinces the limitation of formal computation models in reflecting subtle distinctions in space utilization efficiencies significant in practical contexts. While real-world space-bounded resource tradeoffs between linear, polynomial, and exponential space use exhibit tangible impacts on computation feasibility, conventional models fail to capture such nuanced delineations.

Table of Contents

For any function f(n), we can construct an abstract machine using O(f(n)) space. Yet there exist clear real-world phase transitions in tractability between space functions that complexity classes fail to differentiate. This discontinuity between the smooth hierarchy suggested by space constructibility in formal models and precipitous drops in real-world viability as space resources scale hints that existing models overlook key attributes of the relationship between information processing and physical space constraints.

Relating Space Complexity to Physical Constraints

The connection between mathematically defined space complexity classes and real-world space-imposed efficiency limitations emerges most saliently for problems dealing with physical systems. As Clay Mathematics Institute president Jim Carlson noted, “It seems significant that physics – the science most grounded in the real world – motivated the concept of polynomial-time computation.” The traction gained by time complexity in illuminating phase transitions in computational feasibility resulted partly from its correlation with laws governing dynamic physical processes.

Likewise, relating space complexity to spatial constraints imposed by physics on information processing may offer analogous dividends. Physical information processing invariably entails an encoding process mapping information onto physical degrees of freedom of storage media. The exponentiating of encodings as problem sizes scale quickly binds real-world computations. Concrete space resources – surfaces, volumes, component densities – determine maximal information content, mirroring space complexity bounds. Clarifying these connections may yield space complexity notions aligning better with real-world efficiency crossovers.

Insights from Collapse Results

The non-collapse results for time complexity classes, most iconically P vs. NP, underscore distinctions in optimal algorithms between classes. In contrast, for space classes, we encounter myriads of collapse results, where complexity classes seemingly different in formal models turn out containing the same problems. Such collapses imply that the models fail to capture actual space utilization differences significant in practice. Rather than eradicating hierarchy, these collapses highlight model deficiencies in embedding realistic space efficiencies.

Notably, for multi-tape Turing machines, L, NL, NC, and P all collapse to equally powerful classes. However, real computing with its tape drives, RAM, and caches clearly differentiates in feasibility between linear, logarithmic, parallel and serial polynomial space use. More reflective models capturing such tangible differentiating factors may yield alternate hierarchies aligning truer with real-world phase transitions between easy, hard, harder, and intractable as space resources tighten.

Example Code Demonstrating Space Hierarchy Theorems

We present code instantiating key space hierarchy theorem constructs, aiming to build intuition on their space complexities to prise apart subtle differences. Implementing even simplified versions of such algorithms on real computing substrates helps relating space measures to physical capacities and limitations. Highlighted examples include:

Savitch’s Theorem constructive proofs (PSPACE = NPSPACE)
Immerman–Szelepcsényi Theorem variants (NL = coNL)
Turing machine simulations in small space classes
L vs. NL graph traversal algorithms
ukin1991’s NL vs. NP algorithm

While abstract complexity bounds for these algorithms appear cleanly separated, real-world executions expose gaps between models and practical space-efficiency crossovers. Implementations bring algorithmic space costs closer to physical realities than asymptotic abstractions.

Beyond Worst-Case Analysis: Average-Case Complexity

Worst-case analysis causes complexity theory to overlook much latent structure within complexity classes. Real-world instances often possess exploitable attributes making them more tractable than pathological worst cases. The probabilistic method and average-case analysis reveal rich intricacies within classes deemed featureless in worst settings. Similarly, for space classes, probabilistic instance analysis may unveil smoother borders and graded hierarchies aligned better with real-world space-efficiency transitions.

Subtle space utilization gaps likely manifest between many adjacent sub-polynomial space complexity classes given non-pathological, real-world data distributions. However, since nearly all separation results rely essentially on constructing pathological instances, current theory cannot exclude the possibility of smoother average-case hierarchies concealed by worst-case collapse results. In practical data settings, we may yet find rich problem structure neatly populating small space classes where worst-case assumptions suggest vacancy.

New Models for Sub-Polynomial Space Classes

The shortage of natural problems clearly situating in narrow bands between L and PSPACE, despite reverse abundance in the time domain, signals the need for computing models better capturing real-world space-efficiency crossovers. Reframed models should tie space measures to limits of physical computational substrates, including communication channels, multiprocessing constraints, memory hierarchies, and precision-space tradeoffs.

Hybrid time-space complexity may also provide sharper delineations of sub-polynomial distinctions. For instance, the complexity class DTISP(poly(n), polylog(n)) – distinguishing polylog space use with polynomial sequential time versus polylog time with polynomial space – differentiates efficiencies with tangible real-world implications despite identical worst-case polynomial space requirements in conventional models.

Approximation algorithms also demonstrate that space utilization inefficiencies below polynomial levels induce soluble vs insoluble phase transitions for problems otherwise similarly situated computationally. Reframed models may reinforce such empirical observations with truer separation results.

Open Questions and Future Research Directions

Many questions remain regarding the puzzling paucity of natural problems residing in sub-polynomial space classes:

Can examples of logically simple yet space-constrained concepts like BLOCKED TQBF advance our intuitive understanding of space measures?
Are there probabilistic model formalisms capturing average-case hierarchies within space classes?
Can physical limits on information encoding and processing bound space complexity measures?
Is there complexity-theoretic insight to be gained from fine-grained time-space classes?
Can approximation algorithms exposing space-efficiency phase transitions suggest refined decision models?

The path ahead remains unclear regarding natural problems typifying narrow bands between L and PSPACE. However, reconciling space complexity notions with the physics of computation and information may yet unveil currently concealed structure populating small space classes. As Nobel Laureate David Deutsch posited, “Quantum theory is testable and has been tested and will always be tested by reality itself. Likewise any ultimate theory of reality itself, including computational complexity theory, must pass the test of explaining what is observable or it is wrong.” Bridging observed phase changes in computational space-efficiency with complexity-theoretic models will enable them to better mirror reality.