Kurt Mehlhorn
ABSTRACT
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial classes are generated by running time. They posses a modified Ritchie-Cobham property. A polynomial class is a complexity class iff it is honest.
Starting from the observation that many results about subrecursive classes hold for all reducibility relations (e.g. primitive recursive in, elementary recursive in), which were studied so far, we define abstract subrecursive reducibility relation. Many results hold for all abstract subrecursive reducibilities.
- 1.Axt, P., "On a Subrecursive Hierarchy and Primitive Recursive Degrees", TAMS, 92(1959), 85-105.Google Scholar
Cross Ref
- 2.Cobham, A., "The Instrinsic Computational Difficulty of Functions", Logic, Methodology and Philosophie of Science, Proc. 1964 Conference, North Holland, Amsterdam, 1965.Google Scholar
- 3.Constable, R.L., "Type Two Computational Complexity", 5th ACM Symposium on Theory of Computing, 1973. Google ScholarDigital Library
- 4.Constable, R.L. and A.B. Borodin, "Subrecursive Programming Languages Part I: Efficiency and Program Structure", JACM, 19,3, July 1972. Google ScholarDigital Library
- 5.Cook, S.A., "The Complexity of Theorem Proving Procedures", 3rd ACM Symposium on Theory of Computing, 1971. Google ScholarDigital Library
- 6.Grzegorczyk, A., "Some Classes of Recursive Functions", Rozprawy Matematyczne, Warsaw 1953.Google Scholar
- 7.Hartmanis, J. and J. Hopcroft, "An Overview of the Theory of Computational Complexity", JACM, 18,3, July 1971. Google ScholarDigital Library
- 8.Hopcroft, J. and J. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, 1969. Google ScholarDigital Library
- 9.Jones, N.D., "Recursibility among Combinatorial Problems in log space", Princeton Conference, 1973.Google Scholar
- 10.Ladner, R.E., "Subrecursive Reducibilities", TR 73-03-13, Computer Science Group, University of Washington.Google Scholar
- 11.Lynch, N., "Relativization of the Theory of Computational Complexity", Project MAC, TR-99. Google ScholarDigital Library
- 12.Machtey, M., "Augmented Loop Languages and Classes of Computable Functions", JCSS, 6,6, Dec. 1972.Google Scholar
- 13.Machtey, M., "On a Notion of Helping", 14th SWAT Symposium, 1973.Google Scholar
- 14.Machtey, M., "Honesty Techniques and Polynomial Degrees", Project MAC Conference on Concrete Complexity, 1973.Google Scholar
- 15.Mehlhorn, K., "The 'Almost All' Theory of Subrecursive Degrees is Decidable", TR 73-170, Computer Science Department, Cornell University.Google Scholar
- 16.Meyer, A.R. and D.M. Ritchie, "A Classification of the Recursive Functions", Zeitschr. fur math. Logik, Vol. 18, 1972.Google Scholar
- 17.Mostowski, "Ueber gewisse universelle Relationen", Ann. Soc. Polon. Math., 17 (1938).Google Scholar
- 18.Ritchie, R.W., "Classes of Predictably Computable Functions", Pacific Journal of Math., 1965.Google Scholar
- 19.Rogers, Jr., H., Theory of Recursive Functions and Effective Computability, New York, 1967. Google ScholarDigital Library
- 20.Strong, H.R., "Algebraically Generalized Recursive Function Theory", IBM J. Res. Develop. Google ScholarDigital Library
- 21.Weihrauch, K., Doctoral Dissertation, Bonn.Google Scholar
Index Terms
- Polynomial and abstract subrecursive classes
Recommendations
Polynomial and abstract subrecursive classes
The reducibility ''polynomial time computable in'' for arbitrary functions isintroduced. It generalizes Cook's definition from sets to arbitrary functions. A complexity-theoretic as well as a syntactic characterization is given and their equivalence is ...
On the density of honest subrecursive classes
The relation of honest subrecursive classes to the computational complexity of the functions they contain is briefly reviewed. It is shown that the honest subrecursive classes are dense under the partial ordering of set inclusion. In fact, any countable ...
Comments