On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
Harry B. Hunt · Journal of the ACM · 1982
Umform NP-hard and PSPACE-hard lower bounds are presented for problems for various classes of flowchart and loop program schemes and programming languages These lower bounds hold for the isomorphism, strong equivalence, containment, weak equivalence, totality, divergence, and executabthty problems.These lower bounds hold for any reasonably nontrivial flowchart and loop programming language.