Even Simple Programs Are Hard To Analyze

ABSTRACT

A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondeterministic linear space complexity. Extensions to the language are defined (adding arithmetic and array data structures) and their complexity properties are explored. It is concluded that questions about halting, equivalence, optimization, and so on are intractable even for very simple programming languages.

REFERENCES

• 1: CONSTABLE, R L , AND MUCHNICK, S S Subrecursive program schemata i, II. I Undeodable eqmvalence problems; II Deodable equivalence problems J. Comptr System Sct 6, 6 (Dec 1972), 480-537
• 2: T. V. Griffiths, The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines, Journal of the ACM (JACM), v.15 n.3, p.409-413, July 1968 [doi>10.1145/321466.321473]
• 3: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 4: JONES, N D Space-bounded reducibility among combinatorial problems J Comptr. System Sct 11, 1 (Aug. 1975), 68-85.
• 5: Jot~Es, N D, LIEN, Y.E, AND LAASER, W T New problems complete for nondetermmlst~c log space Comptr Scl. Tech Rep TR-75-1, U of Kansas, Lawrence, Kansas, Aprd 1975
• 6: MEYER, A.R, AND RrrcmE, D M. Computational Complexity and Program Structure. Res Paper RC- 1817, IBM T J Watson Res Ctr, Yorktown Heights, N Y , May 1967
• 7: SEIFERAS, J I, FISCHER, M J , AND MEYER, A R Refinements of the nondetermmlsUc time and space hlerarch~es Conf. Rec 14th Ann IEEE Symp on Switching and Automata Theory, Oct 1973. pp. 130- 137
• 8: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 9: YANOV, Y.I The logical schemes of algorzthms Problems Cybernet. (USSR) 1 (1960), 82-140 (English translation)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Languages, Performance, Theory, Verification