Closure operations on measures of computational complexity
Tóm tắt
In this paper, after a suitable characterization of computational complexity measures, we analyze some closure operations defined on the class of all measures with respect to a given acceptable Gödel numebering. Such a class is a distributive lattice without universal bounds. The problem of the invariance of the class of measures changing the Gödel numbering is finally considered.
Tài liệu tham khảo
Adrianopoli, F. andA. De Luca,Alcune proprietà algebriche delle misure di complessità, di calcolo, Atti del Congresso di Cibernetica di Casciana Terme (Pisa), (1971), 757–768.
Ausiello, G.,Teoria della complessità di calcolo, Calcolo7 (1970), 387–408.
Birkhoff, G.,Lattice Theory, 3rd ed. American Mathematical Society, Colloquium Publications, vol. 25, Providence, R. I., (1967).
Blum, M.,A machine-independent theory of the complexity of recursive functions, J. ACM14 (1967), 322–336.
Davis, M.,Computability and Unsolvability, (1958), McGraw Hill, New York.
De Luca, A. andF. Adrianopoli,Some algebraic properties of computational complexity measures, abstract, Notices of AMS19 (1972), 451.
Hartmanis, J. andJ. E. Hopcroft,An overview of the theory of computational complexity, J. ACM18 (1971), 444–475.
Rogers, H. Jr.,Gödel numberings of partial recursive functions, J. Symbolic Logic:23 (1958), 331–341.
Rogers, H. Jr.,Theory of recursive functions and effective computability, (1967), McGraw-Hill, New York.