×
Young, Paul

Easy constructions in complexity theory: Gap and speed-up theorems. (English) Zbl 0328.68044

Proc. Am. Math. Soc. 37, 555-563 (1973).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0328.68044

Cited in 9 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
03D20 Recursive functions and relations, subrecursive hierarchies
PDF BibTeX XML Cite
\textit{P. Young}, Proc. Am. Math. Soc. 37, 555--563 (1973; Zbl 0328.68044)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Leonard Bass and Paul Young, Ordinal hierarchies and naming complexity classes, J. Assoc. Comput. Mach. 20 (1973), 668 – 686. · Zbl 0339.68038
[2] Manuel Blum, A machine-independent theory of the complexity of recursive functions., J. Assoc. Comput. Mach. 14 (1967), 322 – 336. · Zbl 0155.01503
[3] Manuel Blum, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18 (1971), 290 – 305. · Zbl 0221.02016
[4] A. Borodin, Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19 (1972), 158 – 174; corrigendum, ibid. 19 (1972), 576. · Zbl 0261.68024
[5] Robert L. Constable, The operator gap, J. Assoc. Comput. Mach. 19 (1972), 175 – 183. · Zbl 0229.68016
[6] J. Hartmanis and J. E. Hopcroft, An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18 (1971), 444 – 475. · Zbl 0226.68024
[7] John P. Helm, On effectively computable operators, Z. Math. Logik Grundlagen Math. 17 (1971), 231 – 244. · Zbl 0245.02036
[8] John Helm and Paul Young, On size vs. efficiency for programs admitting speed-ups, J. Symbolic Logic 36 (1971), 21 – 27. · Zbl 0258.68023
[9] E. McCreight and A. Meyer, Classes of computable functions defined by bounds on computation, Proc. First Annual ACM Sympos. on Theory of Computing, pp. 79-88. · Zbl 1283.03074
[10] Albert R. Meyer and Patrick C. Fischer, Computational speed-up by effective operators, J. Symbolic Logic 37 (1972), 55 – 68. · Zbl 0249.68018
[11] A. Meyer and R. Moll, Honest bounds for complexity classes of recursive functions, Project MAC Report, April 1972. · Zbl 0322.02038
[12] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967.
[13] Paul Young, Speed-ups by changing the order in which sets are enumerated, Math. Systems Theory 5 (1971), 148 – 156. · Zbl 0218.68004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.