An overview of computational complexity
---
paper_title: Classes of predictably computable functions

paper_content:

0. Introduction. In this paper we study a sequence of classes of computable functions for which a prediction of the complexity of the calculation may be made in a comparatively simple fashion. The class of recursive functions is accepted as being the class of just those functions for which there is a mechanical procedure for obtaining the values from the arguments. However, this class, since it involves all computations, must involve arbitrarily complex computations. Various more restricted classes of functions have been proposed as being somehow more easily computable, but the greater ease of computation has largely been left on the level of intuition. The notable exception to this is the class F of functions computable(') by finite automata. However, this class is too severely restricted; it does not even include multiplication. We present a hierarchy of more inclusive classes of functions, each defined as the class of functions whose computational complexity is "predictable" by a function in the preceding class. It is known that the class F of numerical functions computable by finite auto
---
paper_title: Storage Modification Machines

paper_content:

In 1970 the author introduced a new machine model [A. Schonhage, Universelle Turing Speicherung, Dorr, Hotz, eds., Automatentheorie and Formale Sprachen, Bibliogr. Institut, Mannheim, 1970, pp. 369–383] now called storage modification machine (SMM). This paper gives a comprehensive presentation of our present knowledge of SMMs. It contains a complete description of the SMM model and its real time equivalence to the so-called successor RAMS. The preliminary version [A. Schonhage, Real-time simulation of multidimensional Turing machines by storage modification machines, Technical Memorandum 37, M.I.T. Project MAC, Cambridge, MA, 1973] of our proof for the real time simulation of multi-dimensional Turing machines is now worked out in its details. Moreover we show the existence of an SMM that performs integer-multiplication in linear time. The final discussion contains a brief comment on the relationship between SMMs and Kolmogorov algorithms [A. N. Kolmogorov and V. A. Uspenskii, On the definition of an algo...
---
paper_title: On the optimal evaluation of a set of bilinear forms

paper_content:

Abstract Although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defined a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. The problem of minimizing the number of multiplications required to perform a calculation leads to a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank-one matrices. In this paper we make a systematic attack on this problem and derived some general results which unify and extend numerous known results.
---
paper_title: Storage Modification Machines

paper_content:

In 1970 the author introduced a new machine model [A. Schonhage, Universelle Turing Speicherung, Dorr, Hotz, eds., Automatentheorie and Formale Sprachen, Bibliogr. Institut, Mannheim, 1970, pp. 369–383] now called storage modification machine (SMM). This paper gives a comprehensive presentation of our present knowledge of SMMs. It contains a complete description of the SMM model and its real time equivalence to the so-called successor RAMS. The preliminary version [A. Schonhage, Real-time simulation of multidimensional Turing machines by storage modification machines, Technical Memorandum 37, M.I.T. Project MAC, Cambridge, MA, 1973] of our proof for the real time simulation of multi-dimensional Turing machines is now worked out in its details. Moreover we show the existence of an SMM that performs integer-multiplication in linear time. The final discussion contains a brief comment on the relationship between SMMs and Kolmogorov algorithms [A. N. Kolmogorov and V. A. Uspenskii, On the definition of an algo...
---
paper_title: An algorithm for the machine calculation of complex Fourier series

paper_content:

An efficient method for the calculation of the interactions of a 2' factorial ex- periment was introduced by Yates and is widely known by his name. The generaliza- tion to 3' was given by Box et al. (1). Good (2) generalized these methods and gave elegant algorithms for which one class of applications is the calculation of Fourier series. In their full generality, Good's methods are applicable to certain problems in which one must multiply an N-vector by an N X N matrix which can be factored into m sparse matrices, where m is proportional to log N. This results inma procedure requiring a number of operations proportional to N log N rather than N2. These methods are applied here to the calculation of complex Fourier series. They are useful in situations where the number of data points is, or can be chosen to be, a highly composite number. The algorithm is here derived and presented in a rather different form. Attention is given to the choice of N. It is also shown how special advantage can be obtained in the use of a binary computer with N = 2' and how the entire calculation can be performed within the array of N data storage locations used for the given Fourier coefficients. Consider the problem of calculating the complex Fourier series N-1 (1) X(j) = EA(k)-Wjk, j = 0 1, * ,N- 1, k=0
---
paper_title: Riemann's hypothesis and tests for primality

paper_content:

In this paper we present two algorithms for testing primality of an integer. The first algorithm runs in 0(n1/7) steps; while, the second runs in 0(log4n) step but assumes the Extended Riemann Hypothesis. We also show that a class of functions which includes the Euler phi function are computationally equivalent to factoring integers.
---
paper_title: The complexity of partial derivatives

paper_content:

Abstract Let L denote the nonscalar complexity in k ( x 1 ,…, x n ). We prove L(ƒ,∂ƒ/∂x 1 ,…,∂ƒ/∂x n )⩽3L(ƒ) . Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant.
---
paper_title: Sorting and Searching

paper_content:

The first revision of this third volume is a survey of classical computer techniques for sorting and searching. It extends the treatment of data structures in Volume 1 to consider both large and small databases and internal and external memories.
---
paper_title: The complexity of computing the permanent

paper_content:

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.
---
paper_title: Factoring polynomials over large finite fields*

paper_content:

This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field GF(p m ) to the problem of finding the roots in GF(p) of certain other polynomials over GF(p). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the logarithm of the order of the finite field. Certain observations on the application of these methods to the factorization of polynomials over the rational integers are also included.
---
paper_title: A characterization of the power of vector machines

paper_content:

A new formal model of register machines is described. Registers contain bit vectorswhich are manipulated using bitwise Boolean operations and shifts. Our main results relate the language recognition power of such vector machines to that of Turing machines. A class of vector machines is exhibited for which time on a vector machine supplies, to within a polynomial, just as much power as space on a Turing machine. Moreover, this is true regardless of whether the machines are deterministic or non-deterministic.
---
paper_title: On relating time and space to size and depth

paper_content:

Turing machine space complexity is related to circuit depth complexity. The relationship complements the known connection between Turing machine time and circuit size, thus enabling us to expose the related nature of some important open problems concerning Turing machine and circuit complexity. We are also able to show some connection between Turing machine complexity and arithmetic complexity.
---
paper_title: On the generation of cryptographically strong pseudo-random sequences

paper_content:

In this paper we show how to generate from a short random seed S a long sequence of pseudo-random numbers Ri in which the problem of computing one more Ri value given an arbitrarily large subset of the other values is provably equivalent to the cryptanalysis of the associated Rivest-Shamir-Adleman encryption function.
---
paper_title: Three approaches to the concept of the amount of information

paper_content:

An infinitely variable speed drive mechanism comprising a pair of sun discs mounted on a first shaft for rotation therewith and at least one of said discs being capable of limited axial movement along the shaft and being loaded towards each other, a plurality of planet discs each rotatably mounted on one end of a corresponding arm or fork for rotation about an axis substantially parallel to said first shaft, the other end of each arm or fork being pivotally mounted on a carrier member for movement about an axis substantially parallel to said first shaft said planet discs moving in a plane normal to the axis of rotation and being capable of limited sliding movement along their axis of rotation so that at all times they remain substantially normal to the axis of rotation, said carrier being mounted on a second shaft for rotation therewith about an axis coaxial with the axis of rotation of said first shaft, a pair of spaced non rotating annular members substantially coplanar with and concentric with said sun discs, the inner periphery of said annular members and the outer periphery of said sun discs embracing and frictionally engaging said planet discs and means for varying the radial position of said planet discs with respect to said annular members and said sun discs.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---

Title: An Overview of Computational Complexity

Section 1: Early Papers
Description 1: Write about the foundational work in computational complexity, highlighting seminal papers by Turing, Rabin, Cobham, and others.

Section 2: Early Issues and Concepts
Description 2: Discuss the initial exploration of the right complexity measures, including time and space, and notable models and theories proposed during the early stages.

Section 3: Upper Bounds on Time
Description 3: Highlight significant algorithms developed since 1960, discussing their efficiency and importance in computational complexity.

Section 4: Lower Bounds
Description 4: Examine the challenges and successes in proving lower bounds on the complexity of specific problems, including diagonal arguments and hierarchical results.

Section 5: Natural Decidable Problems Proved Infeasible
Description 5: Explore notable results proving the infeasibility of certain natural problems, including exponential lower bounds on computation time and space.

Section 6: Structured Lower Bounds
Description 6: Detail the concept of structured lower bounds, where the complexity is proven within restricted computational models.

Section 7: Time-Space Product Lower Bounds
Description 7: Discuss lower bounds on the product of time and space in recognizing specific problems, highlighting important results and open questions.

Section 8: NP-Completeness
Description 8: Describe the theory of NP-completeness, its significance in computational complexity, and key historical developments.

Section 9: #P-Completeness
Description 9: Introduce the concept of #P-completeness and its importance in understanding the intractability of certain functions, with examples.

Section 10: Probabilistic Algorithms
Description 10: Discuss the development and impact of probabilistic algorithms in solving deterministic combinatorial problems.

Section 11: Synchronous Parallel Computation
Description 11: Explore the theory of large-scale synchronous parallel computation, its models, and its implications for future computational complexity research.

Section 12: The Future
Description 12: Summarize the current state and future directions in the field of computational complexity, emphasizing emerging areas and anticipated breakthroughs.