An Overview of the Theory of Computational Complexity
---
paper_title: A Machine-Independent Theory of the Complexity of Recursive Functions

paper_content:

The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations. A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program. A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.
---
paper_title: Upward and Downward Diagonalization over Axiomatic Complexity Classes

paper_content:

This report considers special cases of the question ``What conditions on u() and t() guarantees that $R^{\Phi}_{t}() \neq $R^{\Phi}_{u}()$?'''' where $R^{\Phi}_{t}()$ is the class of recursive functions whose $\Phi$ complexity is bounded by t(). In particular the condition $\stackrel{inf}{n\rightarrow\infty} \frac{t(n)}{u(n)} = 0$ and $\stackrel{lim}{n\rightarrow\infty} \frac{t(n)}{u(n)} = 0$ are examined, and it is shown that certain results of Hartmanis, Stearns and Hennis are in one sense the best possible. It is then shown that the diagonalization techniques used in results of this type are of two different sorts, upward and downward. The differences are made precise and very general conditions are found under which each type applies. These conditions widely generalize several well-known results for time and tape complexity measures. In the final section, the report considers some properties of a special class of names for complexity classes. The techniques used in Lemma 3.3 and Theorems 5.1 and 7.1 are new and promise wider application. Also, new results of Borodin and McCreight and Meyer are used, but otherwise the methods are those of Blum.
---
paper_title: Computational Complexity of One-Tape Turing Machine Computations

paper_content:

The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences, and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a nonregular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.
---
paper_title: On the size of machines

paper_content:

In this paper, the methods of recursive function theory are used to study the size (or cost or complexity) of machines. A positive result of this study shows that to a remarkable degree, the relative size of two machines is independent of the particular way in which machine size is measured. Another result suggests that in order for programs to be of economical size, the programming language must be powerful enough to compute arbitrary general recursive functions, rather than some restricted subset such as the primitive recursive functions. Finally, a kind of speedup theorem is proved which is curiously independent of whether the measure of complexity be the size or the number of steps taken by the machines that compute the functions.
---
paper_title: Unsolvability considerations in computational complexity

paper_content:

The study of Computational Complexity began with the investigation of Turing machine computations with limits on the amounts of tape or time which could be used. Latter a set of general axioms for measures of resource limiting was presented and this instigated much study of the properties of these general measures. Many interesting results were shown, but the general axioms allowed measures with undesirable properties and many attempts have been made to tighten up the axioms so that only desirable measures will be defined. In this paper several undecidability aspects of complexity classes and several sets associated with them will be examined. These sets will be classified by their degree of unsolvability and restrictions will be placed on measures so that these degrees are identical. This gives rise to a new criterion for the “naturalness” of measures and to suggestions for strengthening the measures of complexity.
---
paper_title: Hierarchies of memory limited computations

paper_content:

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined
---

Title: An Overview of the Theory of Computational Complexity

Section 1: Introduction
Description 1: Provide an overview of the motivation for studying computational complexity and discuss the primary aim of the paper, which includes outlining the central concepts, results, and techniques in the theory of computational complexity.

Section 2: Computational Complexity Measures
Description 2: Discuss the concept of computational complexity measures, their definitions, examples, and basic properties. Describe conditions required for a function to be considered a valid computational complexity measure.

Section 3: Speed-Up Theorem and Applications
Description 3: Present the Speed-Up Theorem, provide a new proof, and discuss its implications, including the existence of functions with no best algorithms and applications related to computer programs and different computing machines.

Section 4: Complexity Classes
Description 4: Define complexity classes and explore the results related to bounding the computational complexity of functions, constructing new complexity classes, and illustrating the gap theorem that shows the limits of recursively increasing complexity.

Section 5: Simulation and Parallelism
Description 5: Discuss the process of diagonalizing over complexity classes, simulating computations, and running computations in parallel. Provide results specific to various computational models, such as time-bounded and tape-bounded Turing machines.

Section 6: Naming of Complexity Classes
Description 6: Address the problems of identifying and naming complexity classes, including a discussion on the union theorem and the naming theorem, and demonstrate how well-known subclasses of recursive functions fit into these complexity classes.

Section 7: Size of Machines
Description 7: Investigate the relationship between the size of algorithms and their computational efficiency. Introduce the notion of size measures, and establish the connection between size and complexity, demonstrating the inefficiencies in different sizes of algorithm representations.

Section 8: Historical Notes
Description 8: Provide a brief history of the development of the theory of computational complexity, highlighting key contributions by various researchers and noting important results that have influenced the theory.