An Overview of the Theory of Computational Complexity
From MaRDI portal
Publication:5633652
DOI10.1145/321650.321661zbMath0226.68024OpenAlexW2012030760MaRDI QIDQ5633652
John E. Hopcrofts, Juris Hartmanis
Publication date: 1971
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321650.321661
Related Items
On recursive bounds for the exceptional values in speed-up, Separating the Classes of Recursively Enumerable Languages Based on Machine Size, On the power of recursive optimizers, The intrinsic difficulty of recursive functions, Complexity classes of provable recursive functions, Unnamed Item, Complexity of algorithms and computations, Theory construction in psychology: The interpretation and integration of psychological data, Two types of properties for complexity measures, Computational complexity of formal translations, Meeting of the Association for Symbolic Logic, Dallas 1973, Complexity of computable functions for a generalized storage measure, Algorithmic complexity of recursive and inductive algorithms, Honest bounds for complexity classes of recursive functions, Effective category and measure in abstract complexity theory, The complexity types of computable sets, Effective category and measure in abstract complexity theory, Total complexity and the inference of best programs, Closure operations on measures of computational complexity, A survey of techniques in applied computational complexity, Polynomial and abstract subrecursive classes, The behavioral properties of homogeneous structures, Nonexistence of program optimizers in several abstract settings, Complexity-class-encoding sets, COMPLEXITY AND INFORMATION TECHNOLOGY IN DYNAMIC SYSTEMS, On generalized computational complexity, Complexity metatheorems for context-free grammar problems, Some applications of the McCreight-Meyer algorithm in abstract complexity theory, Relations between diagonalization, proof systems, and complexity gaps, The complexity of the membership problem for some extensions of context-free languagest†, Recursively enumerable complexity sequences and measure independence, A note on complexity measures for inductive classes in constructive type theory, On non-determinacy in simple computing devices, Degrees of computational complexity, Computation of recursive functionals using minimal initial segments, Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems, Unnamed Item, Toward an abstract theory of data compression, Relativization of the Theory of Computational Complexity
