Computational complexity theory, as an important branch of theoretical computer science, systematically characterizes the consumption of time and space resources in computational tasks, providing a solid foundation for understanding the inherent difficulty of various computational problems. Compiler optimization, as a key aspect of improving program design and execution efficiency, involves numerous complex algorithm designs and resource scheduling issues. The computational complexity characteristics of these tasks directly constrain the feasibility and performance of optimization strategies. Based on the classification system of complexity theory, reduction techniques, and complexity boundary analysis, this paper explores in-depth the complexity modeling and theoretical characterization of key tasks in compiler optimization, such as register allocation and instruction scheduling. It discusses scheduling methods for polynomial-time solvable problems, the complexity control mechanisms of approximation algorithms and heuristic strategies, as well as the structural insights that complexity theory provides for the optimization of compiler backends. The research shows that complexity theory not only offers theoretical guidance for the design of compiler optimization algorithms but also promotes the deep integration of theory and engineering practice, driving theoretical innovation and application expansion for efficient compilation technologies.
W. Shao (Fri,) studied this question.