Unsolvability considerations in computational complexity

ABSTRACT

The study of Computational Complexity began with the investigation of Turing machine computations with limits on the amounts of tape or time which could be used. Latter a set of general axioms for measures of resource limiting was presented and this instigated much study of the properties of these general measures. Many interesting results were shown, but the general axioms allowed measures with undesirable properties and many attempts have been made to tighten up the axioms so that only desirable measures will be defined. In this paper several undecidability aspects of complexity classes and several sets associated with them will be examined. These sets will be classified by their degree of unsolvability and restrictions will be placed on measures so that these degrees are identical. This gives rise to a new criterion for the “naturalness” of measures and to suggestions for strengthening the measures of complexity.

REFERENCES

• 1: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 2: Borodin, A. Complexity Classes of Recursive Functions and the Existence of Complexity Gaps, ACM Sym. on Theory of Comp., (May 1969), pp. 67-78.
• 3: Borodin,A., Constable, R., and Hopcroft, J. Dense and Non-Dense Families of Complexity Classes, Tenth Ann. Sym. on Switching and Automata Theory, IEEE (October 1969).
• 4: Constable, R. The Operator Gap, Tenth Ann. Sym. on Switching and Automata Theory, IEEE (October 1969).
• 5: Dekker, J.C.E. and Myhill, J. Some Theorems on Classes of Recursively Enumerable Sets, Trans. AMS, Vol. 89 (1958), pp. 25-59.
• 6: Grzegorczyk, A. Some Classes of Recursive Functions, Rozprawy Matematiyczne, 1953, pp. 1-45.
• 7: Hartmanis, J. and Stearns, R. On the Computational Complexity of Algorithms, Trans. AMS, Vol. 117 (1965), pp. 285-306.
• 8: Lewis, F.D. The Classification of Unsolvable Problems in Automata Theory, Cornell Tech. Report 70-49 (January 1970).
• 9: E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
• 10: Meyer, A. and Fischer P. On Computational Speedup, Ninth Ann. Sym. on Switching and Automata Theory, IEEE (October 1968), pp. 351-355.
• 11: Myhill, J. Linear Bounded Automata, University of Pennsylvania, Report No. 60-22 (June 1960).
• 12: Myhill, J. Creative Sets, Zeit fur Math. Logik und Grund der Math., Vol. 1 (1955), pp. 97-108.
• 13: Péter, Roza. Recursive Functions, 3d Edition, New York, 1967.
• 14: Ritchie, R. Classes of Predictably Computable Functions, Trans.AMS, Vol. 106 (1963), pp. 139-173.
• 15: Robertson, E.L. and Landweber, L.H. On Recursive Properties of Complexity Classes, these proceedings.
• 16: Rogers, H.G. Godel Numberings of Partial Recursive Functions, JSL, Vol. 23 (1958), pp. 331-341.
• 17: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 18: Stearns, R., Hartmanis, J. and Lewis, P., II. Hierarchies of Memory Limited Computations, 1965 IEEE Conf. Rec. on Switching Theory and Log. Design, pp. 179-190.
• 19: Paul R. Young, Toward a Theory of Enumerations, Journal of the ACM (JACM), v.16 n.2, p.328-348, April 1969 [doi>10.1145/321510.321525]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Algorithms, Languages, Theory