Generative Complexity: A Unifying Meta-Framework for Computation as Information Reconstruction

Title: Generative Complexity: A Unifying Meta-Framework for Computation as Information Reconstruction Abstract: This paper introduces Generative Complexity, a novel formal framework that reframes computational problem-solving as a process of stepwise information reconstruction rather than search within a fixed space. We define a computational model based on a generative event library operating on a structured cognitive state, which incrementally reconstructs a solution from background information and constraints. Our central technical contribution establishes that this framework is both rigorous and foundational. We define the class GenFP of problems solvable by polynomially-bounded generative sequences and prove the equivalence GenFP = FP, thereby anchoring our model firmly within classical deterministic polynomial-time computation. We further demonstrate the framework’s utility by formalizing the Boolean Satisfiability Problem (SAT) and the DPLL algorithm within it, showing a direct correspondence between generative sequences and classical algorithmic steps. Beyond this equivalence, the primary conceptual contribution of Generative Complexity is its role as a unifying meta-framework. We provide a structured degeneration map illustrating how major classical complexity paradigms—including P/NP, BPP, IP, APX, and BQP—can be viewed as emerging from specific, constrained subsets of the full generative process. Each class is shown to result from "degeneration operations" that strip away key aspects of generative dynamics, such as historical guidance, incremental structure-building, or coherent information integration. This work provides a new, unified lens for understanding computation, one that is inherently compatible with richer models of reasoning, learning, and physical information processing. It lays a formal foundation for future studies of intelligent and natural computational systems that operate beyond the constraints of classical search-based complexity. Keywords: Computational Complexity, Formal Models, Generative Processes, Meta-Framework, FP, NP, Problem-Solving, Degeneration Operations. References to prior work (for inclusion in Zenodo metadata):This work formalizes and extends the conceptual framework introduced in earlier preprints on Dynamic Generative Theory (DOI:10.5281/zenodo.18322110). It serves as the computational-theoretical foundation for that research program.