On the Computational Complexity of Program Scheme Equivalence
Harry B. Hunt, Robert L. Constable, Sartaj K. Sahni · SIAM Journal on Computing · 1980
The computatiional complexity of several decidable problems about program schemes, recursion schemes, and simple programming languages is considered. The strong equivalence, weak equivalence, containment, halting, and divergence problems for the single variable program schemes and the linear monadic recursion schemes are shown to be $NP$-complete. The equivalence problem for the Loop 1 programming language is also shown to be $NP$-complete. Sufficient conditions for a program scheme problem to be $NP$-hard are presented. The strong equivalence problem for a subset of the single variable program schemes, the strongly free schemes, is shown to be decidable deterministically in polynomial time.