We present a general theoretical framework extending the Hilbert–Krylov Decomposi- tion (HKD) beyond its original application to Subset Sum and its recent exact application to the Traveling Salesman Problem. We formalize HKD as a universal width–collapse operator acting on dynamic programming state spaces for NP-hard problems. Under ex- plicit contraction, admissible bounding, and arithmetic diversity conditions, HKD provably reduces exponential state growth to a bounded effective width while preserving global opti- mality. A complete direction–sketch–proof development is provided, recursively subdivided into fine-grained lemmas. Selected reference code and diagnostic tower outputs are included to illustrate arithmetic structure and referee-facing verification mechanisms.
Keywords
^KEYWORDS^
Conclusion
Together with the Subset Sum and TSP results, this work establishes HKD as a general-purpose framework for collapsing the effective complexity of exact NP-hard solvers under structural regularity.
References
[1]M. S. Yang, Hilbert–Krylov Tower Decomposition and a Pseudo-Polynomial Complexity Bound for Subset Sum, International Journal of Computer Techniques, 12(6), 2025.
[2]M. S. Yang, Hilbert–Krylov Tower Decomposition for the Traveling Salesman Problem: Exact Solutions with Collapsed Effective Complexity, forthcoming.
How to Cite This Paper
Michael S. Yang (2025). Generalizing the Hilbert–Krylov Decomposition to Exact Solution of NP-Hard Problems. International Journal of Computer Techniques, 12(6). ISSN: 2394-2231.
