A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between n log n/k log k and 4n log n/k log k, up to first-order terms in n and k.>

Most new computer architectures are concerned with maximizing performance by providing suitable instruction sets for compiled code and providing support for systems functions. We argue that the most effective design methodology must make simultaneous tradeoffs across all three areas: hardware, software support, and systems support. Recent trends lean towards extensive hardware support for both the compiler and operating systems software. However, consideration of all possible design tradeoffs may often lead to less hardware support. Several examples of this approach are presented, including: omission of condition codes, word-addressed machines, and imposing pipeline interlocks in software. The specifics and performance of these approaches are examined with respect to the MIPS processor.

Let A be a language chosen randomly by tossing a fair coin for each string x to determine whether x belongs to A. With probability 1, each of the relativized classes ${\textbf{LOGSPACE}}^A $, ${\bf P}^A $, ${\bf NP}^A $, ${\bf PP}^A $, and ${\textbf{PSPACE}}^A $ is properly contained in the next. Also, ${\bf NP}^A \ne {\text{co-}} {\bf NP}^A $ with probability 1. By contrast, with probability 1 the class ${\bf P}^A $ coincides with the class ${\bf BPP}^A $ of languages recognized by probabilistic oracle machines with error probability uniformly bounded below $\tfrac{1}{2}$. ${\bf NP}^A $ is shown, with probability 1, to contain a ${\bf P}^A $-immune set, i.e., a set having no infinite subset in ${\bf P}^A $. The relationship of ${\bf P}^A $-immunity to p-sparseness and ${\bf NP}^A $-completeness is briefly discussed: ${\bf P}^A $-immune sets in ${\bf NP}^A $ can be sparse or moderately dense, but not co-sparse. Relativization with respect to a random length-preserving permutation $\pi $, instead of a random oracle A, yields analogous results and in addition the proper containment, with probability 1, of ${\bf P}^\pi $ in ${\bf NP}^\pi \cap {\text{co-}}{\bf NP}^\pi $, which we have been unable to decide for a simple random oracle. Most of these results are shown by straightforward counting arguments, applied to oracle-dependent languages designed not to be recognizable without a large number of oracle calls. It is conjectured that all $p^A $-invariant statements that are true with probability 1 of subrecursive language classes uniformly relativized to a random oracle are also true in the unrelativized case.

The tape requirements of probabilistic and deterministic Turing machine transducers are polynomially related.

In this paper we consider the question of how much space is needed to represent a set. Given a finite universe U and some subset V (called the vocabulary), an exact membership tester is a procedure that for each element s in U determines if s is in V. An approximate membership tester is allowed to make mistakes: we require that the membership tester correctly accepts every element of V, but we allow it to also accept a small fraction of the elements of U - V.

@ NP then ≤mP and ≤TP differ on NP. One method that might prove helpful in settling this conjecture is to exhibit an efficient construction that builds from any nonpolynomial set A a set B such that A ≤TP B but A

A probabilistic Turing machine is a Turing machine with the ability to make decisions based on the outcomes of unbiased coin tosses. The partial function computed by a probabilistic machine is defined by assigning to each input the output which occurs with probability greater than $\frac{1}{2}$. With this definition, only partial recursive functions are probabilistically computable. The run time and tape of probabilistic machines are defined. A palindrome-like language is described that can be recognized faster by one-tape probabilistic Turing machines than by one-tape deterministic Turing machines. It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability. Several classes of languages recognized probabilistically in polynomial time are defined and compared with $NP$.

We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let $\mathcal{P}^X (\text{resp. }\mathcal{NP}^X )$ be the class of languages accepted in polynomial time by deterministic (resp. nondeterministic) query machines with oracle X. We construct a recursive set A such that $\mathcal{P}^A = \mathcal{NP}^A $. On the other hand, we construct a recursive set B such that $\mathcal{P}^B \ne \mathcal{NP}^B $. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes $\mathcal{P}^X $, $\mathcal{NP}^X $, and co $\mathcal{NP}^X $, the family of complements of languages in $\mathcal{NP}^X $. Several related open problems are described.

Let h be a recursive function. A partial recursive function ψ is i.o. (infinitely often) h -complex if every program for ψ requires more than h ( χ ) steps to compute ψ ( χ ) for infinitely many inputs χ . A more stringent notion is that of ψ being a.e. (almost everywhere) h -complex: ψ is a.e. h -complex if every program for ψ requires more than h ( χ ) steps to compute ψ ( χ ) for all but finitely many inputs χ . These two definitions of h -complex functions do not yield the same theorems. Although it is possible to prove of every i.o. h -complex recursive function that it is i.o. h -complex, it is not possible to prove of every a.e. h -complex recursive function that it is a.e. h -complex. Similarly, recursive functions not i.o. h -complex can be proven to be such, but recursive functions not a.e. h -complex cannot be so proven. The construction of almost everywhere complex recursive functions appears much more difficult than the construction of infinitely often complex recursive functions. There have been found no “natural” examples of recursive functions requiring more than polynomial time for all but finitely many inputs. It is shown that from a single example of a moderately a.e. complex recursive function, one can obtain a.e. very complex recursive functions.

A conjecture concerning the codeword compositions of uniquely decipherable codes is proposed. This conjecture is shown to be equivalent to a related conjecture of Karp about the codeword costs of uniquely decipherable codes. A set of inequalities satisfied by ali prefix-condition codes is exhibited, and it is conjectured that these inequalities are valid for all uniquely decipherable codes.