Computational complexity of functions

DOI10.1016/0304-3975(95)00163-8MaRDI QIDQ1351510zbMATH OpenOpenAlexFDO

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1411.3010

Analysis of algorithms and problem complexity (68Q25)

Abstract: Below is a translation from my Russian paper. I added references, unavailable to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75] (see also [Lynch 75]). Earlier relevant work (classical theorems like Compression, Speed-up, etc.) was done in [Tseitin 56, Rabin 59, Hartmanis Stearns 65, Blum 67, Trakhtenbrot 67, Meyer Fischer 72]. I translated only the part with the statement of the results. Instead of the proof part I appended a later (1979, unpublished) proof sketch of a slightly tighter version. The improvement is based on the results of [Meyer Winklmann 78, Sipser 78]. Meyer and Winklmann extended earlier versions to machines with a separate input and working tape, thus allowing complexities smaller than the input length (down to its log). Sipser showed the space-bounded Halting Problem to require only additive constant overhead. The proof in the appendix below employs both advances to extend the original proofs to machines with a fixed alphabet and a separate input and working space. The extension has no (even logarithmic) restrictions on complexity and no overhead (beyond an additive constant). The sketch is very brief and a more detailed exposition is expected later: [Seiferas Meyer].

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Computational complexity of functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1351510)