Summary: "We address the problem of the security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical, but nonetheless highly confidential data, may be in jeopardy. We present a scheme for efficient secure two-party communication with provable ever-lasting security. The security is guaranteed in face of any future technological advances, given the current state of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future.
   "The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all-powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or computational power can help the adversary in deciphering the message.
   "We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of S. L. Braunstein et al. [IEEE Trans. Inform. Theory 46 (2000), no. 4, 1644–1649; MR1768659], employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.''

Let G and H be abelian groups. A function mapping G to H is linear (more conventionally, is homomorphic) if for all x,y∈G, f(x)+f(y)=f(x+y). Intuitively, f is linear if its graph is a straight line on the plane. Two linear functions are consistent if their graphs have the same slope. M. Blum, M. G. Luby and R. Rubinfeld [J. Comput. System Sci. 47 (1993), no. 3, 549–595; MR1248868] initiated the study of linear-consistency testing; their results also have consequences in program checking and for efficient PCP characterizations of NP. The authors of this paper extend this study to testing the linear-consistency of multiple functions. They propose a variant of the test of Blum et al.: For functions f1,f2,f3 mapping G to H, pick x,y∈G uniformly and independently at random and check whether f1(x)+f2(y)=f3(x+y). This test is analyzed for two cases: (1) G and H are arbitrary finite abelian groups, and (2) G=Fn2 and H=F2. For the case (1), the authors show that if the test rejects with probability δ<29, then by changing the value of fi, for each i∈{1,2,3}, on at most a δ fraction of the inputs, a triple of linear-consistent functions is obtained. For the case (2), the authors establish an even stronger result: Every triple of functions accepted by the linear-consistency test with nontrivial probability is nontrivially close to a triple of linear-consistent functions, where "nontrivial'' means with probability strictly larger than 12.
   As an application of their results, the authors give a new, tight PCP characterization of NP: Every language in NP can be accepted by a 1-round 3-prover interactive proof system in which the verifier tosses O(logn) coins, accepts yes-instances with probability arbitrarily close to one, and rejects no-instances with probability at least 12. Formally, for each ϵ>0, NP=MIP1−ϵ, 1/2[O(logn),3,1].

Summary: "We extend the notion of linearity testing to the task of checking linear consistency of multiple functions. Informally, functions are `linear' if their graphs form straight lines on the plane. Two such functions are `consistent' if the lines have the same slope. We propose a variant of a test due to M. Blum, M. G. Luby and R. Rubinfeld [J. Comput. System Sci. 47 (1993), no. 3, 549–595; MR1248868] to check the linear consistency of three functions f1,f2,f3 mapping a finite abelian group G to an abelian group H: Pickx,y∈G uniformly and independently at random and check whether f1(x)+f2(y)=f3(x+y). We analyze this test for two cases: (1) G and H are arbitrary abelian groups and (2) G=Fn2 and H=F2.
   "Questions bearing a close relationship to linear consistency testing seem to have been implicitly considered in recent work on the construction of PCPs (and in particular by Håstad [in STOC '97 (El Paso, TX), 1–10 (electronic), ACM, New York, 1999 MR1715618 ]). This work is abstracted explicitly for the first time here. We give an application of this problem (and of our results): a (yet another) new and tight characterization of NP, namely ∀ϵ>0, NP=MIP1−ϵ,12[O(logn),3,1], i.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(logn) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts an instance of the language with probability 1−ϵ and rejects non-instances with probability at least 12. Such a result is of some interest in the study of probabilistically checkable proofs.''

Summary: "We provide a simple secret-key two-party secure communication scheme, which is provably information-theoretically secure in the limited-storage-space model. The limited-storage-space model postulates an eavesdropper who can execute arbitrarily complex computations, and is only limited in the total amount of storage space (not computation space) available to him. The bound on the storage space can be arbitrarily large (e.g. terabytes), as long as it is fixed. Given this bound, the protocol guarantees that the probability of the eavesdropper gaining any information on the message is exponentially small. The proof of our main results utilizes a novel combination of linear algebra and Kolmogorov complexity considerations.''

The authors show how DNA-based computational methods may be useful in solving problems that are related to biotechnology. Such problems include DNA sequencing, DNA fingerprinting and DNA mutation detection. They do not explicitly show how their methods can be applied to these problems, but they show how a test tube with unknown DNA can be encoded so that DNA-based computational methods can be applied. As biomolecular processes are error prone, the authors make allowances in their model for error. This is a significant difference from previous DNA-based computational models where errors were mainly ignored. The model has three main operations: "cut'', "length separate'' and "anneal''. Each of these operations is given with fixed parameters defining the error rates. It is shown that if a test tube contains equal amounts of k strings, each of distinct length, then for every ϵ one can obtain an ϵ-approximation of a test tube containing only the ith string in O(log(1/ϵ)) steps. This lemma is used to show the main result: It is possible to check whether two unknown strands (DNA strings) of length n are equal in O(lognloglogn) bio-steps with error probability ϵ. The assumption in this case is that each string can be uniquely determined with its set of substrings of length logn. A short discussion of the practicality of the results concludes the article.

It has been known for some time that the introduction of randomization has important consequences for distributed algorithms: one aspect is the breaking of symmetry in otherwise identical processes, but another is more profound—it often increases computational power or decreases computational costs.
   The subject of this paper is the performance gap between deterministic and randomized algorithms for mutual exclusion, as measured by the number of bits required for the shared variable. This figure is Ω(logn) bits for fair mutual exclusion between n processes done deterministically, but just O(loglogn) bits randomized—a result established by Rabin [J. Comput. System Sci. 25 (1982), no. 1, 66–75; MR0685361]. The main result of this paper is to prove a tight lower bound of Ω(loglogn) bits. Although this result is useful, in that a loose end is tied up, perhaps of greater interest is the technique by which the result was achieved, which was by relating the fairness of mutual exclusion algorithms to the liveness of Markov chains (where a chain is live if in each of its first n steps it has a "considerable probability'' of visiting a state not previously visited). The bounds for mutual exclusion are then established by proving bounds on the size of the matrix representing the Markov chain and the number of states of the Markov chains.
   The original Rabin algorithm used an O(loglogn)-bit shared variable and had the so-called linear fairness property that if m processes compete for a critical section, each process has probability Ω(1/m) of entering next. However, no lower bounds were known, although it was quite widely held that a constant-sized shared variable should be sufficient. Indeed, Rabin [op. cit.] showed a constant-sized variable could deliver Ω(1/n) probability of entry, but this was independent of m.
   The paper reviewed here also defines a slightly weaker form of fairness, called polynomial fairness, such that the entry probability is Ω(1/m1+ϵ). In fact, for all positive nonzero values of ϵ, only an O(logloglogn)-bit shared variable is necessary: a significant size reduction for a correspondingly small reduction in fairness. One additional result is that a constant-sized variable is shown to guarantee an entry probability of Ω(1/2m).

Summary: "Lotteries with the unique maximum property and the unique winner property are considered. Tight lower bounds are proven on the domain size of such lotteries.''

Summary: "We consider the problem of simulating synchronous computations on asynchronous shared memory systems. The systems we consider allow for arbitrary asynchronous behavior of the processors. In addition, we make very limited (and in some cases no) assumptions about the atomicity of read and write operations to shared memory. We provide detailed definitions of these asynchronous systems and their atomicity properties.
   "The first construction in this paper is a novel clock for asynchronous systems. The clock is a basic tool for synchronization in the asynchronous environment. The construction we give is extremely robust, and can be implemented in a system with no atomicity assumptions, and in the presence of an adaptive adversary scheduler. The correct behavior of the clock is obtained with overwhelming probability (>1−2−αn, α>0).
   "We then show how to harness this clock to drive an efficient PRAM simulation on an asynchronous system. The simulation requires an O(log2n) work, and O(logn) space, overhead. This improves by a logn factor on the efficiency of previously obtained simulation results, while relaxing the assumptions on the underlying asynchronous system.''

For integers d,m≥1, let fd(m) denote the minimum t such that, for any hypergraph F={F1,⋯,Ft} whose maximum degree is d, there exists a nonempty subfamily F0 such that |⋃F∈F0F|≡0 (mod m). The main result of this paper is Theorem 1. If q is a prime power then fd(q)=d(q−1)+1. The paper includes a proof that fd(m) also denotes the minimum t such that for any h∈Z[x1,⋯,xt] which satisfies h(0)=0 and degreeh<d, there exists a nonzero ε∈{0,1}t such that h(ε)≡0 (mod m).

Summary: "An information dispersal algorithm (IDA) is developed that breaks a file F of length L=|F| into n pieces Fi, 1≤i≤n, each of length |Fi|=L/m, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of the lengths |Fi| is (n/m)⋅L. Since n/m can be chosen to be close to 1, the IDA is space efficient. IDA has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission of information in networks, and to communications between processors in parallel computers. For the latter problem, provably time-efficient and highly fault-tolerant routing on the n-cube is achieved, using just constant size buffers.''

The authors give a new randomized (Monte Carlo) algorithm for finding a maximum (cardinality) matching in an arbitrary graph. Their algorithm is conceptually simpler than combinatorial algorithms involving blossoms, and has a running time of O(M(n)nlognloglogn) bit operations, where M(n) is the number of arithmetic operations required for multiplying two n×n matrices. The authors give an alternative proof of Lovász' generalization of Tutte's theorem, and show that it extends to finite fields. This is used to obtain an O(M(n)log2n) randomized algorithm for computing the size of a maximum matching. The proof schema enables the authors to develop a randomized algorithm for finding a perfect matching in a graph, which substitutes randomly over Zp for the variables of the Tutte matrix, and uses n/2 matrix inversions to find a perfect matching (if the Tutte matrix is nonsingular). The two algorithms are then combined to give a randomized (Monte Carlo) algorithm for finding a maximum matching, which can be extended to a Las Vegas algorithm using Lovász' method. The authors also present some partial results on the parallel complexity of matching, which make use of this algebraic approach.

Summary: "We present randomized algorithms to solve the following string-matching problem and some of its generalizations: Given a string X of length n (the pattern) and a string Y (the text), find the first occurrence of X as a consecutive block within Y. The algorithms represent strings of length n by much shorter strings called fingerprints, and achieve their efficiency by manipulating fingerprints instead of longer strings. The algorithms require a constant number of storage locations, and essentially run in real time. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional pattern-matching problems.''

The authors suggest that modal logics for operators such as `it is conceivable that' and `it is reasonably likely to be a consistent hypothesis that' may provide a fruitful means of reasoning about likelihood nonquantitatively, without appeal to probabilities, especially in decision-theoretic contexts. A logic of this sort is constructed and its possible uses in medical diagnosis and proofs of the correctness of protocols for swapping secrets are discussed. The logic is supplied with a possible-worlds semantics, and is shown to have the finite model property and to be decidable in exponential time.

Two well-known theorems of Lagrange state that every positive integer can be expressed as a sum of four integral squares, and every integer not of the form 4a(8m+7) is a sum of three integral squares. The purpose of the paper under review is to describe several efficient randomized algorithms for the construction of such representations. The algorithms are nontrivial and make use of numerous results in number theory, including an algorithm for the representation of a prime p≡1mod4 as a sum of two squares.
   A few of the references given are incomplete. Reference [1] has appeared [L. M. Adleman, D. Estesand the reviewer, Math. Comp. 48 (1987), no. 177, 17–28]. Reference [6] has also appeared [Estes, Adleman, K. Kompella, the reviewer and G. L. Miller, in Advances in Cryptology—CRYPTO '85 (Santa Barbara, Calif., 1985), 3–13, Lecture Notes in Comput. Sci., 218, Springer, Berlin, 1986; MR0851418]. Reference [16] [J. M. Pollardand C.-P. Schnorr, "Solution of x2+ky2≡m(modn), with application to digital signatures''] is to appear in IEEE Trans. Inform. Theory rather than Math. Comp.

From the introduction: "In the present paper we employ the fingerprinting method to solve a string matching problem. Given a string y we want to find the earliest repetition, i.e., the shortest w and x such that y=wxxz. We call this the repetition problem.
   "This question was treated by A. Apostolico and F. P. Preparata[Theoret. Comput. Sci. 22 (1983), no. 3, 297–315; MR0693062], who gave an O(|y|log|y|) algorithm for this problem and some of its extensions. M. G. Main and R. J. Lorentz[this collection, see heading, 271–278; see MR0815327] gave a linear-time algorithm for recognition of square-free strings. Both papers use the suffix tree method. The Main-Lorentz reduction of complexity to linear running time employs the O(log|y|) size of the computer word to encode information and string operations.
   "We give a very simple algorithm for discovering repetitions by use of fingerprints. If y∈Σ∗, |Σ|=s, |y|=m then the expected running time is O(mlog2mlogsm). But by further use of the power of encoding several operations into one machine-word operation, the running time can be reduced to O(mlog2m), and perhaps even further. An additional feature of this algorithm is its parallelizability. An n-processor machine (n≤m) would produce approximately an n−1 reduction in running time. This would produce practical improvements even for small values of n.''

Author's summary: "We propose protocols for implementing contract signing, confidential disclosures, and certified mail in an electronic mail system. These transactions are provably impossible without a trusted intermediary. However, they can be implemented with just a small probability of a participant cheating his partner, by use of a beacon emitting random integers. Applications include privacy protection of personal information in data banks, as well as the protection of business transactions.''

Author's summary: "The problem of implementing mutual exclusion of N asynchronous parallel processes in a model where the primitive communication mechanism is a test-and-set operation on a shared variable has been the subject of extensive research. While a two-valued variable suffices to ensure mutual exclusion, it was shown by J. E. Burns et al. [J. Assoc. Comput. Mach. 29 (1982), no. 1, 183–205; MR0662618] that N/2 values are necessary to avoid lockout of any process, and N+1 values are required to ensure bounded waiting time. We introduce the idea of employing randomization in the mutual exclusion protocol and achieve a mutual exclusion solution, which is with probability 1 lockout-free and bounded-waiting, using just a 4⋅log2N-valued shared variable. The protocol is extremely simple, easy to implement, and avoids certain undesirable features present in some of the other solutions. The protocols of the processes are identical and this symmetry is preserved throughout the computation. In particular, in contrast to the systems of Burns et al. [op. cit.], no single process ever becomes, even temporarily, controller of the computation, which would make everything depend on it.''

Author's summary: "In the course of a concurrent computation, processes P1,⋯,Pn must reach a common choice of one out of k alternatives A1,⋯,Ak. They do this by protocols using k shared variables, one for each alternative. If the range of the variables has m values then 12n−−√3≤m is necessary, and n+2≤m is sufficient, for deterministic protocols solving the choice coordination problem (C.C.P.). We introduce very simple randomizing protocols which, independently of n, solve the C.C.P. by use of a fixed alphabet. A single-byte (256-valued) alphabet permits a solution with nontermination probability smaller than 2-127. Many software and hardware tasks involving concurrency can be interpreted as choice coordination problems. Choice coordination problems also occur in nature.''

The authors discuss the complexity of certain standard algebraic calculations with special rules for counting the number of multiplications and divisions used. Use is made of algebraic field theory. Let F⊂Ω be two fields and let E and K be intermediate fields. The sum and difference of two numbers in any field is negligible. The product of two numbers belonging to F also does not count, nor does the ratio of two numbers when the denominator belongs to F. The main theorem can be stated as follows: Let D be a matrix whose elements belong to K. Let the column vector V consist of elements of E that are linearly independent over F. Let t be the degree of transcendence of D over F. Then any algorithm that will compute the product DV must contain at least [t/2] multiplications and divisions.
   {For the entire collection in which the second paper appears see MR0648291.}

The author presents probabilistic methods for finding irreducible polynomials of degree n, roots of polynomials, and for polynomial factoring into irreducible factors over finite fields GF(pn). The running times of Berlekamp's algorithms for computation in finite fields are improved upon by measuring complexity as the expected number of operations to be performed. For example, the expected number of steps for finding an irreducible polynomial g(x)∈Zp[x] of degree n is O(n3⋅log2n⋅loglogn⋅logp). The straightforward nature of the methods, together with the good probable running times, should make these methods very suitable for real computations in finite fields.

The author reports on several experiments that he and V. Pratt have performed using his probabilistic algorithm for primality testing [the author, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), pp. 21–39, Academic Press, New York, 1976; MR0464678]. For example, 2300—163 is probably the largest prime less than 2300. Again, let M be the product of all primes less than 300. If n=338M+821, then n and n+2 have 123 digits and are probably primes.

From the introduction: "We propose a signature system employing any block-encoding device and based, in one essential aspect, on probabilistic logic. A different signature system can be based on the Diffie-Hellman proposal [W. Diffie and M. E. Hellman, IEEE Trans. Inform. Theory 22 (1976), no. 6, 644–654; MR0437208] of public-key cipher systems. An algorithm for such a public key-system employing large prime numbers was discovered by the author (unpublished) and independently by R. L. Rivest, L. Adleman and A. Shamir [Comm. ACM 21 (1978), 120–126; Zbl 368 #94005]. The properties of the encoding function which are needed for rendering the signature system secure are stated in Section 3 in axiomatic form.
   "The axioms themselves are assumptions about the intractability of certain computations involving the encoding function. The notion of intractability required for ensuring the soundness of an encoding function is different from and stronger than the existing concept in complexity theory. In Section 10 we briefly touch on the methodological questions pertaining to secure communications and signatures. We introduce the notion of universal intractability required for a sound theoretical foundation of this field.''

The author lists minor corrections to his original paper [MR0451859].

We discuss the authors' contributions individually.
   Enderton [MR3727417]: This paper is an excellent introduction to recursion theory. Starting from the intuitions of informal computability, the author defines the class of recursive functions (functionals) via Turing machines (with oracles) and discusses normal forms and the halting problem. Next comes recursive enumerability and its relationship to recursively axiomatizable theories. Two sections are devoted to degrees—Turing, many-one, and one-one—and include basic facts about creative and simple sets and the jump operator. The definability of recursive relations over the natural numbers leads to a discussion of the arithmetical and analytical hierarchies. The final section deals with recursive analogues of classical objects—countable ordinals and real numbers.
   The breadth of coverage dictates that few proofs are included, but whenever possible, good heuristic arguments are given. The pace of the latter sections will be difficult for beginning students, but the mature reader will come away with a good feeling for the flavor and content of elementary recursion theory.
   Davis [MR3727418]: After reformulating the halting problem in terms of Turing machines, the author gives complete proofs that there are in general no algorithms to decide: (1) the word problem for semi-Thue and Thue systems; (2) the word problem for finitely presented semigroups; (3) whether or not a Post correspondence system has a solution; (4) whether or not two context-free phrase structure grammars generate disjoint languages; (5) whether or not a context-free phrase structure grammar is ambiguous. Other unsolvable problems discussed without complete proofs; (6) the word problem for (presentations of) groups; (7) whether or not a group is trivial; (8) whether or not a given two-dimensional simplicial complex is simply connected; (9) whether or not two given manifolds of dimension ≥4 are homeomorphic; (10) whether or not a given Diophantine equation has an integer solution; (11) the validity problem for first-order logic (Entscheidungsproblem). Several of the important steps for (10) are given and careful references are provided for all omitted steps. There is no discussion of specific undecidable theories, but this is the only failing of an exemplary exposition.
   Rabin [MR3727419]: A theory is decidable just in case there is an algorithm for determining when a given formula is a theorem of the theory. Formally this means that the set of Gödel numbers of theorems is a recursive set of numbers, but proofs of decidability tend to have a less formal character than proofs of undecidability and the last step of converting the algorithm into a proof of recursiveness is usually omitted. The emphasis here is on the flavor of the algorithms which have been constructed for deciding various theories. Most proofs are sketches which could in most cases be filled in by the diligent reader but which succeed in conveying the basic ideas involved even to the less diligent one.
   The author divides the methods used into three basic classes—elimination of quantifiers, model-theoretic, and interpretations. As examples of the first are offered the theories of discrete orderings (in detail), Presburger arithmetic and real-closed fields (briefly sketched), and dense linear orderings, algebraically closed fields, and Boolean algebras (mentioned). Among model-theoretic methods are uses of Vaught's test on categoricity in power to establish decidability of the theories of dense linear orderings and algebraically closed fields, and the model completeness/prime model route to the decidability of real closed fields. Other methods involving elementary chains and direct products are mentioned briefly. The proofs by interpretation are all based on the author's tree theorem, which establishes the decidability of the monadic second-order theory of two successor functions. The proof of the tree theorem is only hinted at. Among the applications we find the decidability of the theory of linearly ordered sets, the monadic second-order theory of the Cantor discontinuum with quantifiers over closed sets, the theory of Boolean algebras with a sequence of distinguished ideals, and various nonclassical logics.
   A final section discusses modern complexity theory, which addresses the question of the practicability of algorithms. All known algorithms for deciding theories are at least exponentially complex—for infinitely many n there is a formula ϕ with at most n symbols such that the algorithm requires at least 2n steps to decide whether or not ϕ is a theorem. Several of the algorithms mentioned above are shown to have complexity of the form 22n (Presburger arithmetic) or even hyper-exponential (linear orderings). The article ends with a discussion of the classes P (problems solvable by some algorithm having only polynomial complexity) and NP (problems solvable by some nondeterministic algorithm having polynomial complexity).
   Simpson [MR3727420]: As the author points out, the emphasis in the theory of degrees of unsolvability has been on methods rather than results. Most expositions of the subject are organized around techniques rather than theorems. In this fairly brief overview of degree theory the author aims to "present those theorems whose statements alone shed the most light on the structure and uses of degrees''.
   Two sections are devoted to the algebraic structure of the degrees with the join operation and with or without the jump operator. The highlight is the author's recent result that the theories of these structures are recursively isomorphic to the truth set of second-order arithmetic. Section Four describes the few extant results on these structures which depend on set-theoretic hypotheses beyond ZFC. Section Five is a very brief survey of recursively enumerable degrees and degrees below 0′, and Section Six deals with the basis problem for (relativized) co-r.e. subsets of 2ω.
   Although the treatment is quite brief, considering the size and complexity of the subject, a fairly coherent picture emerges. However, to get a full appreciation for the richness of the theory, the reader with no previous exposure to degree theory would be well advised to consult some of the other survey articles mentioned.
   Shore [MR3727421]: The history of α-recursion theory, the convergence of threads from all of the main subareas of logic to give the subject its start in the middle 1960's, is a fascinating study. In the opening sections of this paper the author sketches this development as well as is possible in a few pages. The emphasis is on recursion theory as he leads us through the definition of α-recursive function via Kripke's equation calculus, the selection of the proper domains (admissible α) via the criterion that all deductions be of length at most α, and the generalizations of finiteness via the connection with the corresponding level Lα of the hierarchy of constructible sets. There follows a discussion of the evolution of the notion "α-recursive in'' and a sketch of the current status of the theory of α-r.e. sets. To give the reader a taste of the methods of the subject the author guides us through a nicely done conceptual proof of the splitting theorem: Given a regular α-r.e. but not α-recursive set C, there are disjoint α-r.e. sets A and B, both strictly α-recursive in C, such that A∪B=C. Section Four discusses some of the impact of α-recursion theory on its founding disciplines, set theory and recursion theory in particular. The paper concludes with an excellent annotated bibliography, which should be of great use to anyone wishing to pursue the subject further.
   Kechris/Moschovakis [MR3727422]: In their introduction the authors observe that higher-type recursion is considered "difficult and somewhat esoteric'', even by logicians of other persuasions. Kleene's original definition, which in the nearly 20 years since its appearance has been modified but not essentially changed, is fairly complicated and based on intuitions which have not been found universally compelling. This paper provides not only a firmer foundational framework for the subject but also a vastly improved technical setting for development of the theory.
   The central idea is that in any context the "recursive'' partial functions are those which can be "built up'' inductively by simple and natural processes. Induction has always played a leading role in recursion theory, but this approach shows clearly how many of the basic results are in fact special cases of more general results in the theory of inductive definability.
   The paper is in two parts. In the first is developed a general notion of recursion over any set A. The second part applies and expands this theory for the case where A is the finite-type structure over the natural numbers. Let x,y,z denote elements of A; f,g,h partial functions An→A; and Φ,Ψ,Θ partial functionals with arguments of type (x¯¯¯,f¯¯¯), where bars signify finite sequences, and values in A. Φ is said to be functional if and only if for some n its arguments are of type (x¯¯¯,f,g¯¯¯) with x¯¯¯∈An and f n-ary. With such a Φ associate a map on partial functions f↦Φ[g¯¯¯](f)=λx.Φ(x¯¯¯,f,g¯¯¯) and a transfinite sequence of partial functions fξ defined by fξ=Φξ(x¯¯¯,g¯¯¯)=Φ[g](⋃η<ξfη). The functional Φ∞(x¯¯¯,g¯¯¯)=(⋃ξfξ)(x¯¯¯) is said to be inductively defined by Φ. If I is a set of functionals, Ψ is said to be I-recursive if and only if for some Φ∈I,Ψ(x¯¯¯,g¯¯¯)=Φ∞(n¯¯¯,x¯¯¯,g¯¯¯) for some finite sequence n¯¯¯ of natural numbers. To yield an interesting class, I must have a few closure properties. If I0[Θ¯¯¯¯] is the smallest class containing Θ¯¯¯¯ with these properties, the I0[Θ¯¯¯¯]-recursive functionals are said to be recursive in Θ¯¯¯¯.
   Various special cases fall easily into this framework: ordinary recursion theory corresponds to I0-recursion restricted to ω⊆A; recursion in a type-2 functional F:ωA→ω is I0[ΘF]-recursion, where ΘF(f)= (F(f), if f is total, unary; undefined, otherwise); recursion in a quantifier Q⊆P(A) is I0−[F#Q]-recursion, where F#Q(f)= (0, if {x:f(x)=0}∈Q; 1, if {x:f(x)=0 or f(x) is undefined} ∉Q; undefined, otherwise). With a few restrictions on Θ¯¯¯¯, a large part of recursion theory can be done in this general setting: the first and second recursion theorems hold, functional substitution preserves recursiveness, and there are enumeration and prewellordering theorems for the class of semirecursive relations with all their usual consequences. Indeed, this is all achieved with much less pain than in most more specialized presentations.
   For the application to types over ω, take A=T∗, where T(0)=ω,T(j+1) is the set of total unary functions T(j)→ω, and T∗ is the set of finite sequences of elements of T=⋃j∈ωT(j). The functionals studied by Kleene are functions T(j0)×⋯×T(jn)→ω and hence are partial functions A→A. In particular, elements of T are also partial functions. The classes of functionals used here to generate recursion theories have some additional closure properties which reflect the type structure. If K0[Θ¯¯¯¯] is the smallest class containing Θ¯¯¯¯ with these properties, then the K0[Θ¯¯¯¯]-recursive functionals are called Kleene recursive in Θ¯¯¯¯. From this point of view, Kleene's original definition consists in specifying a particular Φ∈K0 and defining ϕ to be partial recursive if an only if for some e∈ω, ϕ(x¯¯¯)=Φ∞(e,x¯¯¯). Thus every such function is recursive in the current sense; the most difficult theorem of the paper is the converse assertion.
   The remainder of the paper develops more of the theory of higher-type recursion—the substitution theorems and the closure properties of envelopes of normal functionals. The final section contains a guide to the recent literature.
   Aczel [MR3727423]: Of all the notions of definability currently in vogue, inductive definability has perhaps the longest and richest history. The idea of repeatedly applying some operations or rules to build up the smallest collection of objects closed under these operations has played a role in many parts of mathematics for a very long time. It is only quite recently, however, that this mode of definition has been studied and the general properties of inductively defined collections worked out. For the logician, one of the first examples that comes to mind is the set of theorems of a formal system, the smallest set of formulas which contains the axioms and is closed under the rules of inference. The author uses this example as a starting point to explain the general notion of a (usually monotone) operator and shows that any inductive definition can in a sense be considered as a formal system.
   In recursion theory inductive definability is intimately connected with the notion of recursive enumerability and its generalizations. The similarities of the classes of Σ01 and Π11 sets of natural numbers can be largely explained by the fact that these classes are closed under inductive definability. Much of the rest of the article is devoted to exploring the analogues of these facts for definability over an abstract structure. For Σ01 there is a complete analogy: Under some assumptions which ensure that the structure is sufficiently rich, a relation is inductively definable by a positive existential operator if and only if it is itself existentially definable. The proof runs via a third characterization, being representable in a suitable formal theory T. In the Π11 case the analogy is complete only for countable structures, but it is still true in general that a relation is inductively definable by a positive operator if and only if it is representable in the extension of T obtained by adjoining the infinitary rule: From all instances θ(a) conclude ∀xθ(x). The theory of this class of relations is sketched along with its relativization to a monotone quantifier.
   The final section briefly treats nonmonotone inductions, inductions over an admissible set, and formal systems in which inductive definability is a primitive notion.
   Martin [MR3727424]: The development of descriptive set theory is an interesting case study in the progress of mathematics. After the subject arose around the turn of the century, it flowered through the 1930's but then apparently died. Using hindsight, however, we see that the subject merely shifted gears around 1940—the results of Kleene, Mostowski, and others on hierarchies arising from recursion theory turned out to be refinements and extensions of the classical work. These strands were joined by Addison in the late 1950's and the enriched theory saw some further developments, but the main problems that had led to its downfall remained. The first four sections of this paper give a good account of this stage of the theory. It is a tribute to the elegance of the modern viewpoint that it is possible in such a short space to give a nearly complete development with proofs.
   In the last ten years the subject has seen an enormous increase in popularity. The key element was the discovery that various set-theoretical hypotheses beyond ZFC could be used to settle the previously intractable questions. The axiom of constructibility, the existence of measurable cardinals, and, most of all, projective determinacy have yielded answers to almost all of the classical questions and a good many more. These results are surveyed in the last two sections, mainly without proof.
   Other topics touched on are the independence results which prove that the classical problems really were undecidable in ZFC and the further consequences for descriptive set theory of the full axiom of determinacy.
   {For the entire collection see MR0457132.}

From the editor's foreword: "The Handbook of Mathematical Logic is an attempt to share with the entire mathematical community some modern developments in logic. We have selected from the wealth of topics available some of those which deal with the basic concerns of the subject, or are particularly important for applications to other parts of mathematics, or both.
   "Mathematical logic is traditionally divided into four parts: model theory, set theory, recursion theory and proof theory. We have followed this division, for lack of a better one, in arranging this book. It made the placement of chapters where there is interaction of several parts of logic a difficult matter, so the division should be taken with a grain of salt. Each of the four parts begins with a short guide to the chapters that follow. The first chapter or two in each part are introductory in scope. More advanced chapters follow, as do chapters on applied or applicable parts of mathematical logic. Each chapter is definitely written for someone who is not a specialist in the field in question. On the other hand, each chapter has its own intended audience which varies from chapter to chapter. In particular, there are some chapters which are not written for the general mathematician, but rather are aimed at logicians in one field by logicians in another.''

Table of Contents:

Jon Barwise, "Foreword”, p. vii.

"Contributors”, pp. viii-ix.

   Part A. Model theory MR0491125: Jon Barwise, An introduction to first-order logic (pp. 5–46) MR3727402; H. Jerome Keisler, Fundamentals of model theory (pp. 47–103) MR3727403; Paul C. Eklof, Ultraproducts for algebraists (pp. 105–137) MR3727404; Angus Macintyre, Model completeness (pp. 139–180) MR3727405; Michael Morley, Homogenous sets (pp. 181–196) MR3727406; K. D. Stroyan, Infinitesimal analysis of curves and surfaces (pp. 197–231) MR3727407; M. Makkai, Admissible sets and infinitary logic (pp. 233–281) MR3727408; A. Kock and G. E. Reyes, Doctrines in categorical logic (pp. 283–313) MR3727409.
   Part B. Set theory MR0540758: J. R. Shoenfield, Axioms of set theory (pp. 321–344) MR3727410; Thomas J. Jech, About the axiom of choice (pp. 345–370) MR3727411; Kenneth Kunen, Combinatorics (pp. 371–401) MR3727412; John P. Burgess, Forcing (pp. 403–452) MR3727413; Keith J. Devlin, Constructibility (pp. 453–489) MR3727414; Mary Ellen Rudin, Martin's axiom (pp. 491–501) MR3727415; I. Juhász, Consistency results in topology (pp. 503–522) MR3727416.
   Part C. Recursion theory [MR0485262]: Herbert B. Enderton, Elements of recursion theory (pp. 527–566) MR3727417; Martin Davis, Unsolvable problems (pp. 567–594) MR3727418; Michael O. Rabin, Decidable theories (pp. 595–629) MR3727419; Stephen G. Simpson, Degrees of unsolvability: a survey of results (pp. 631–652) MR3727420; Richard A. Shore, α-recursion theory (pp. 653–680) MR3727421; Alexander S. Kechris and Yiannis N. Moschovakis, Recursion in higher types (pp. 681–737) MR3727422; Peter Aczel, An introduction to inductive definitions (pp. 739–782) MR3727423; Donald A. Martin, Descriptive set theory: projective sets (pp. 783–815) MR3727424.
   Part D. Proof theory and constructive mathematics MR0491063: C. Smoryński, The incompleteness theorems (pp. 821–865) MR3727425; Helmut Schwichtenberg, Proof theory: some applications of cut-elimination (pp. 867–895) MR3727426; Richard Statman, Herbrand's theorem and Gentzen's notion of a direct proof (pp. 897–912) MR3727427; Solomon Feferman, Theories of finite type related to mathematical practice (pp. 913–971) MR3727428; A. S. Troelstra, Aspects of constructive mathematics (pp. 973–1052) MR3727429; Michael P. Fourman, The logic of topoi (pp. 1053–1090) MR3727430; Henk P. Barendregt, The type free lambda calculus (pp. 1091–1132) MR3727431; Jeff Paris and Leo Harrington, A mathematical incompleteness in Peano arithmetic (pp. 1133–1142) MR3727432; Index of names (pp. 1143–1150); Subject index (pp. 1151–1165).
   {The parts will be reviewed individually.}

The author discusses central topics of the theory of complexity of computations and gives a selection of prominent results. Among the topics discussed are: complexity of general recursive functions, algebraic calculations, computer arithmetic, speed of parsing, data processing, intractable problems in automatic theorem proving, the P=NP problem, probabilistic algorithms, and problems of secure communication.

A new approach to the study of probabilistic algorithms is presented in this paper. The author shows that when randomization is incorporated into an algorithm the result can be a very efficient algorithm. Two examples are given: nearest pair in a set of points in k-space, and compositeness checking.
   The primality algorithm is very efficient because it selects (at random) a number and then checks to see if that number is a certificate of compositeness for the prime. Since there would be many of these certificates for any number not prime, the odds that the algorithm provides a correct answer are quite good.
   {For the entire collection see MR0426474.}

A later version of this paper has appeared [J. Comput. System Sci. 12 (1976), no. 2, 198–221; MR0428807].
   {For the entire collection see MR0408289.}

This paper starts with the observation that there are always short, true statements within such elementary logical systems as the theory of addition of natural numbers (Presburger's arithmetic), the shortest proof of which is impossibly long. This points to the difficulty of building general theorem provers on a computer. The author examines this problem in the context of observed behavior by human mathematicians, and he conjectures that success of human mathematical reasoning may be due to sharp specialization in limited domains. He next examines several basic combinatorial problems for which there is considerable suggestive evidence that their complexity is exponential. Since AI is concerned with the solution of certain combinatorial problems, and in view of what we now know about the complexity characteristics of these problems, the author warns that AI may be facing tasks that are demonstrably not feasible. But clearly, a major objective of AI research has been to find methods for handling various phenomena of problem complexity by focusing on special subdomains of a domain, developing heuristic search approaches, etc. The author recognizes that this has been the approach of many investigators. He stresses, however, the difficulties inherent in the implementation of such approaches and he makes proposals for further research in this area. He suggests defining a measure over a space of problems that is based on a notion of "semantic content''. Furthermore, he discusses the desirability of developing algorithms that are well tailored for limited subclasses of a problem class, and others that allow the production of errors in certain cases.
   This paper provides a valuable link between current work in complexity theory and AI. The title is somewhat misleading. The paper is more about the theoretical context within which AI research is proceeding, rather than about theoretical impediments to work in AI.
   {For the entire collection see MR0383806.}

Authors' summary: "Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first-order theory of the real numbers under addition, and Presburger arithmetic—the first-order theory of addition on the natural numbers. There is a fixed constant c>0 such that for every (non-deterministic) decision procedure for determining the truth of sentences of real addition and for all sufficiently large n, there is a sentence of length n for which the decision procedure runs for more than 2cn steps. In the case of Presburger arithmetic, the corresponding bound is 22cn. These bounds apply also to the minimal lengths of proofs for any complete axiomatization in which the axioms are easily recognized.''
   {For the entire collection, see MR0351142.}

The author considers m affine functions li in Rn, a fixed convex set C of Rn and for x∈Rn the predicate SP(x) defined by SP(x)⇔⋀i(li(x)≥0). Then he compares, for a given x0∈Rn, the computational effort involved in checking: x0∈C∧SP(x0); in proving: x0∈C∧SP(x0). By a complete (polynomial) proof in C of SP(x), relative to Q (a polynomial) the author means an r×k array of polynomials: P=(pij(x)) such that (1) for all x0∈Rn, for all i≤r, (x0∈C) and ⋀j=1⋯k(pij(x0)≥0)⇒SP(x0); (2) for all x0∈C, there exists an i≤r, In fact, the specification "relative to Q'' may be dropped in this definition and more generally pij(x) and Q(x) are allowed to be meromorphic functions (quotients of analytic functions in C). The number k is defined as width (P).
   The main theorem states that if li(x) are sign-independent and P a complete (meromorphic) proof in C of SP(x), relative to Q (where Q≠0 in C), then m≤width(P). The proof is given in the polynomial case (the method involved adapts immediately to the meromorphic case). Moreover, by suitable counterexamples, if hypothesis of meromorphicity (pij(x) together with Q(x)) or sign-independence of lj is dropped, the conclusion is invalidated. Another theorem (with only a sketched proof) says that a complete linear (i.e., first degree polynomial) proof P for SP(x) exists with width (P)=n+1.
   As a corollary which concerns the travelling salesman problem on n cities: proving the minimality of a tour would involve O(n4) steps, while checking the minimality of a tour would involve O(n!) steps.
   {For the entire collection see MR0349057.}