A new method for fault-tolerant wormhole routing in arbitrary dimensional meshes is introduced. The method was motivated by certain routing requirements of an initial design of the Blue Gene supercomputer at IBM Research. The machine is organized as a three-dimensional mesh containing many thousands of nodes and the routing method should tolerate a few percent of the nodes being faulty. There has been much work on routing methods for meshes that route messages around faults or regions of faults. The new method is to declare certain nonfaulty nodes to be "lambs." A lamb is used for routing but not processing, so a lamb is neither the source nor the destination of a message. The lambs are chosen so that every "survivor node," a node that is neither faulty nor a lamb, can reach every survivor node by at most two rounds of dimension-ordered (such as e-cube) routing. An algorithm for finding a set of lambs is presented. The results of simulations on 2D and 3D meshes of various sizes with various numbers of random node faults are given. For example, on a 32 /spl times/ 32 /spl times/ 32 3D mesh with 3 percent random faults and using at most two rounds of e-cube routing for each message, the average number of lambs is less than 68, which is less than 7 percent of the number 983 of faults and less than 0.21 percent of the number 32,768 of nodes.

We prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective decommitment problem. An adversary is given commitments to a collection of messages, and the adversary can ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are unopened. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a "magic function" that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function.It follows easily from definitions that if a 3-round public-coin argument system is zero-knowledge in the standard (fairly strong) sense, then it has no magic function. We define a weakening of zero-knowledge such that zero-knowledge ⇒ no-magic-function still holds. For this weakened form of zero-knowledge, we give a partial converse: informally, if a 3-round public-coin argument system is not weakly zero-knowledge, then some form of magic is possible for this argument system. We obtain our definition of weak zero-knowledge by a sequence of weakenings of the standard definition, forming a hierarchy. Intermediate forms of zero-knowledge in this hierarchy are reasonable ones, and they may be useful in applications. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment.

In-place reconstruction of differenced data allows information on devices with limited storage capacity to be updated efficiently over low-bandwidth channels. Differencing encodes a version of data compactly as a set of changes from a previous version. Transmitting updates to data as a version difference saves both time and bandwidth. In-place reconstruction rebuilds the new version of the data in the storage or memory the current version occupies-no scratch space is needed for a second version. By combining these technologies, we support highly mobile applications on space-constrained hardware. We present an algorithm that modifies a differentially encoded version to be in-place reconstructible. The algorithm trades a small amount of compression to achieve this property. Our treatment includes experimental results that show our implementation to be efficient in space and time and verify that compression losses are small. Also, we give results on the computational complexity of performing this modification while minimizing lost compression.

We construct 2-round (i.e., 2-message), public-coin, black-box (concurrent) zero-knowledge proof systems and arguments for any language in NP under the assumption that the prover is resource-bounded during the execution of the protocol.

The subject of this article is differential compression , the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in O ( n ) time and O (1) space in the worst case (where each unit of space contains [log n ] bits), as compared to algorithms that run in O ( n ) time and O ( n ) space or in O ( n 2 ) time and O (1) space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.

An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least 10 125 gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe. This result and its proof, due to both authors, originally appeared in 1974 in the Ph.D. thesis of the first author. In this article, the proof is given, the result is put in historical perspective, and the result is extended to probabilistic circuits.*

The goal of this paper is to establish links between computational complexity theory and the theory and practice of constrained block coding. In particular, the complexities of several fundamental problems in constrained block coding are precisely classified in terms of the existing complexity-theoretic structure. One type of problem studied is that of designing encoder and decoder circuits using minimum or approximately minimum hardware; for our purposes, an "input" to this problem is (i) a deterministic, irreducible finite-state transition diagram (DIF) defining a set of constrained binary sequences, and (ii) a desired rate p:q. Several of these minimum-encoder and minimum-decoder problems are shown to be NP-hard, and more interestingly some are shown to be complete in the second and third levels of the polynomial hierarchy. Another fundamental problem is that of computing the maximum rate of a block code; that is, given a DIF and a codeword length q, find the maximum p such that a rate p:q block code exists for the constraint defined by the DIF. This problem is shown to be NP/sup #P/-complete. Although it is not known whether NP/sup #P/ contains problems of super-polynomial complexity, it lies "higher" in the complexity-class structure than NP in the sense that it is possible, given current knowledge, that NP/sup #P/ contains problems of super-polynomial complexity even if P=NP. Another question studied is whether maximum rate block codes can always be implemented by encoders and decoders of polynomial size. The answer to this question is shown to be closely related to whether the class #P lies "lower" in the complexity-class structure than currently believed-a proof of either answer would have major implications in complexity theory.

The goal of this paper is to establish links between computational complexity theory and the theory and practice of constrained block coding. The complexities of several fundamental problems in constrained block coding are shown to be complete in various classes of the existing complexity-theoretic structure. The results include (relatively rare) /spl Sigma//sub 2//sup p/-, /spl Sigma//sub 3//sup p/, and NP/sup PP/-completeness results. Two types of problems are considered: (1) the problem of designing encoder and decoder circuits using minimum or approximately minimum hardware for a given constraint and a given rate; (2) computing the maximum rate of a block code for a given constraint and codeword length. In both cases, a constraint is specified by a deterministic finite state transition diagram. Another question studied is whether maximum-rate block codes can always be implemented by encoders and decoders of polynomial size. The answer to this question is shown to be closely related to the complexity of PP.

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six desirable properties for ideal layouts; however no declustered layout satisfying all properties has been published in the literature. We present a complete, constructive characterization of the collection of ideal declustered layouts possessing all six properties. Given that ideal layouts exist only for a limited set of configurations, we also present two novel layout families. PRIME and RELPR can tolerate multiple failures in a wide variety of configurations with slight deviations from the ideal. Our simulation studies show that the new layouts provide excellent parallel access performance and reduced incremental loads during degraded operation, when compared with previously published layouts. For large accesses and under high loads, response times for the new layouts are typically smaller than those of previously published declustered layouts by a factor of 2.5.

It is a well-known result of Fagin that the complexity class NP coincides with the class of problems expressible in existential second-order logic (El), which allows sentences consisting of a string of existential second-order quantifiers followed by a first-order formula.Monadic NP is the class of problems expressible in monadic Cl, i.e., Xi with therestriction that the second-order quantifiers are all unary, and hence range only over sets (as opposed to ranging over, say, binary relations), For example, the property of a graph being 3colorable belongs to monadic NP, because 3colorability can be expressed by saying that there exists three sets of vertices such that each vertex is in exactly one of the sets and no two vertices in the same set are connected by an edge.Unfortunately, monadicNPis notarobustclass, inthatitisnotclosed under first-order quantification.We define closed monadic NP to be the closure of monadic NP under first-order quanthlcation and existential unary second-order quantification.Thus, closed monadic NP differs from monadic NP in that we allow the possibility of arbitrary interleavings of tirstorder qunntifiers among the existential unary second-order quantifiers, We show that closed monadic NP is a natural, rich, and robust subclass of NP.As evidence for its richness, we show that not only is it a proper extension of monadic NP, but that it contains properties not in various other extensions of monadic NP.In particular, we show that closed monadic NP contnins an undirected graph property not in the closure of monadic NP under first-order quantification and Boolean operations, Our lower-boundproofsrequire a number of new game-theoretic techniques.*The full vcrnlon of this pnpcr, including proofs, can be obtaioed from: hltp://v/wv~,nlmadcn,ibm.comlcs/people/ 'This is xcessible from the finite model theory home page ut httpz~/speedy.informatkwth-aachen.dcAVWW~.html.

To provide a logic for reasoning about concurrently executing programs, Abrahamson has defined an extension of propositional dynamic logic (PDL) by allowing interleaving as an operator for combining programs, in addition to the regular PDL operators union, concatenation, and star. We show that the satisfiability problem for interleaving PDL is complete for deterministic double-exponential time, and that this problem requires time double-exponential in cnlog n for some positive constant c. Moreover, this lower bound holds even when restricted to formulas where each program appearing in the formula has the form a1¦a2¦ … ¦ak where ¦ denotes the interleaving operator and where a1, …, ak are regular programs, i.e., programs built from atomic programs using only the regular operators. Another consequence of the method used to prove this result is that the equivalence problem for regular expressions with interleaving requires space 2cnlog n and that this lower bound holds even to decide whether (E1¦E2¦ … ¦Ek) ∪ F ≡ ∑∗ where E1, …, Ek, F are ordinary regular expressions; this improves a previous result of the authors. Moreover, the same lower bound holds for the containment problem for expressions of the form E1¦E2¦ … ¦Ek.

The purpose of this paper is a study of computation that can be done locally in a distributed network, where “locally” means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: • There are nontrivial LCL problems that have local algorithms. • There is a variant of the dining philosophers problem that can be solved locally. • Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. • It is undecidable, in general, whether a given LCL has a local algorithm. • However, it is decidable whether a given LCL has an algorithm that operates in a given time t. • Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs).

We consider regular expressions extended with the interleaving operator, and investigate the complexity of membership and inequivalence problems for these expressions. For expressions using the operators union, concatenation, Kleene star, and interleaving, we show that the inequivalence problem (deciding whether two given expressions do not describe the same set of words) is complete for exponential space. Without Kleene star, we show that the inequivalence problem is complete for the class Σp2 at the second level of the polynomial-time hierarchy. Certain cases of the membership problem (deciding whether a given word is in the language described by a given expression) are shown to be NP-complete. It is also shown that certain languages can be described exponentially more succinctly by using interleaving.

Upper and lower bounds are proved for the time complexity of the problem of reaching agreement m a distributed network m the presence of process fwlures and inexact information about time.It is assumed that the amount of (real) time between any two consecutwe steps of any ncmfatrhy process is at least c1 and at most C2; thus, C = cz/cl is a measure of the timing uncertainty.It E also assumed that the time for message dehvery ]s at most d.Processes are assumed to fail by stopping, so that process fdures can be detected by timeouts.A straightforward adaptation of an (~+ 1)-round round-based agreement algorithm takes time (f + l)Cd If there are f potential faults, while a straightforward mochflcation of the proof that f'+ 1 rounds are required yields a lower bound of time (~+ 1)d.The frost result of this paper is m agreement algorlthm in which the uncerttimty factor C is only incurred for one round, yielding A preliminary version of this work appeared in Proceedings of the 23rd ACM SvrnposamZ on Theon of Corrrputmg (New Orleans, La., May 6-8).ACM, New York, 1991, pp.359-369.

. The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally Checkable Labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: ffl There are non-trivial LCL problems that have local algorithms. ffl There is a variant of the dining philosophers problem that can be solved locally. ffl Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. ffl It is undecidable, in general, whether a given LCL has a local algorithm. ffl However, it is decidable whether a given LCL has an algorithm that operates in a given time t. ffl Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor id's). Keywords: ...

The authors prove a lower bound of Omega (log n/log log n) on the competitive ratio of any (deterministic or randomised) distributed algorithm for solving the mobile user problem on certain networks of n processors. The lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. A similar Omega (log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving a distributed scheduling problem on any of these networks. The proofs combine combinatorial techniques with tools from linear algebra and harmonic analysis and apply, in particular, a generalization of the vertex isoperimetric problem on the hypercube, which may be of independent interest.>

An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.

The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition.

. Upper and lower bounds are proved for the time complexity of the problem of reaching agreement in a distributed network in the presence of process failures and inexact information about time. It is assumed that the amount of (real) time between any two consecutive steps of any nonfaulty process is at least c 1 and at most c 2 ; thus, C = c 2 =c 1 is a measure of the timing uncertainty. It is also assumed that the time for message delivery is at most d. Processes are assumed to fail by stopping, so that process failures can be detected by timeouts. A straightforward adaptation of an (f + 1)-round round-based agreement algorithm takes time (f + 1)Cd if there are f potential faults, while a straightforward modification of the proof that f + 1 rounds are required yields a lower bound of time (f + 1)d. The first result of this paper is an agreement algorithm in which the uncertainty factor C is only incurred for one round, yielding a running time of approximately 2fd + Cd in the worst ca...

It is shown that if a two-way probabilistic finite-state automaton (2pfa) M recognizes a nonregular language L with error probability bounded below $\frac{1}{2}$, then there is a positive constant b (depending on M) such that, for infinitely many inputs x, the expected running time of M on input x must exceed $2^{n^{b}}$ where n is the length of x. This complements a result of Freivalds showing that 2pfa’s can recognize certain nonregular languages in exponential expected time. It also establishes a time complexity gap for 2pfa’s, since any regular language can be recognized by some 2pfa in linear time. Other results give roughly exponential upper and lower bounds on the worst-case increase in the number of states when converting a polynomial-time 2pfa to an equivalent two-way nondeterministic finite-state automaton or to an equivalent one-way deterministic finite-state automaton.

A persuasive coin is a sufficiently unbiased source of randomness visible to sufficiently many processors in a distributed system. An algorithm is described for achieving a persuasive coin in the presence of an extremely powerful adversary where the number of rounds of message exchange among the processors is constant, independent of the number n of processors in the system as well as the number of faults, provided the total number of faulty processors does not exceed a certain constant multiple of $n/\log n$. As a corollary an $\Omega (n/\log n)$-resilient probabilistic protocol for Byzantine agreement running in constant expected time is obtained. Combining this with a generalization of a technique of Bracha, a probabilistic Byzantine agreement protocol tolerant of almost ${n / 4}$ failures with $O(\log \log n)$ expected running time is obtained.

The recognition power of two-way probabilistic finite-state automata (2PFAs) is studied. It is shown that any 2PFA recognizing a nonregular language must use exponential expected time infinitely often. The power of interactive proof systems (IPSs) where the verifier is a 2PFA is also investigated. It is shown that (1) IPSs in which the verifier uses private randomization are strictly more powerful than IPSs in which the random choices of the verifier are made public to the prover. (2) IPSs in which the verifier uses public randomization are strictly more powerful than 2PFAs alone, that is, without a prover; (3) every language accepted by some deterministic Turing machine in exponential time can be accepted by some IPS. Other results concern IPSs with 2PFA verifiers that run in polynomial expected time.>

The distributed firing squad problem is defined in the context of a synchronous distributed system where the correct processors operate in lock-step synchrony but do not share a global clock. If one or more correct processors receive a command to start a firing squad synchronization, then at some future time all correct processors must “fire” (formally, enter a special state) at exactly the same step. For various fault models, upper and lower bounds are proved on the number of faulty processors that can be tolerated and on the number of rounds of communication required between the reception of the start command and firing. For example, if a firing squad protocol is resilient to t fail-stop faults, then at least $t + 1$ rounds are necessary and sufficient. For the case of Byzantine faults with authentication where the faulty processors can take steps in between the synchronous steps of the correct processors, the firing squad problem can be solved in $t + 5$ rounds, provided that $n > 3t$, where n is the number of processors and t is the number of faults, and the problem cannot be solved at all if $n \leqq 3t$. Moreover, in the case that $n \leqq 3t$, the impossibility of a firing squad protocol holds even for a weaker “timing fault model” where all processors generate messages correctly according to the protocol, but the faulty processors can affect the system by slightly slowing down or speeding up messages.

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound Δ on the time required for a message to be sent from one processor to another and a known fixed upper bound Φ on the relative speeds of different processors. In an asynchronous system no fixed upper bounds Δ and Φ exist. In one version of partial synchrony, fixed bounds Δ and Φ exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds Δ and Φ. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T , and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.

We present a randomized parallel algorithm for term matching. Let n be the number of nodes of the directed acyclic graphs (dags) representing the terms to be matched. Then our algorithm uses $O(\log ^2 n)$ parallel time and $M(n)$ processors, where $M(n)$ is the complexity of $n \times n$ matrix multiplication. The randomized algorithm is of the Las Vegas type, that is, the answer is always correct, although with small probability the algorithm might fail to produce an answer. The number of processors is a significant improvement over previously known bounds. Under various syntactic restrictions on the form of the input dags, only $O(n^2 )$ processors are required in order to achieve deterministic $O(\log ^2 n)$ parallel time. Furthermore, we reduce directed graph reachability to term matching using constant parallel time and $O(n^2 )$ processors. This is evidence that no deterministic algorithm can significantly beat the processor bound of our randomized algorithm. We also improve the P-completeness result of Dwork, Kanellakis, and Mitchell on the unification problem, showing that unification is P-complete even if both input terms are linear, i.e., no variable appears more than once in each term.

Reaching agreement is a primitive of distributed computing. Whereas this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: A system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer et al. have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper their work is extended: Several critical system parameters, including various synchrony conditions, are identified and how varying these affects the number of faults that can be tolerated is examined. The proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

One of the more significant achievements of twentieth century mathematics, especially from the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in the 1930's which provided a precise and robust definition of what it means for a problem to be computationally solvable, or decidable, and which showed that there are undecidable problems which arise naturally in logic and computer science. Indeed, when one is faced with a new computational problem, one of the first questions to be answered is whether the problem is decidable or undecidable. A problem is usually defined to be decidable if and only if it can be solved by some Turing machine, and the class of decidable problems defined in this way remains unchanged if “Turing machine” is replaced by any of a variety of other formal models of computation. The division of all problems into two classes, decidable or undecidable, is very coarse, and refinements have been made on both sides of the boundary. On the undecidable side, work in recursive function theory, using tools such as effective reducibility, has exposed much additional structure such as degrees of unsolvability. The main purpose of this survey article is to describe a branch of computational complexity theory which attempts to expose more structure within the decidable side of the boundary. Motivated in part by practical considerations, the additional structure is obtained by placing upper bounds on the amounts of computational resources which are needed to solve the problem. Two common measures of the computational resources used by an algorithm are time, the number of steps executed by the algorithm, and space, the amount of memory used by the algorithm.

We present a distributed protocol for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The protocol can tolerate up to n/log n malicious processor failures where n is the number of processors in the system. The protocol needs only a fixed constant number of rounds of message exchange; no preprocessing is required. As a corollary we obtain an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time. Combining this with a generalization of a technique of Bracha, we obtain a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.

In this paper, we study the complexity of finding an efficient search for combinatorial problems which are commonly solved by backtracking. First, a formalism is introduced. Backtrack searches are ordinarily thought of as following a tree pattern. Our model is considerably more general, and there are problems where this allows much shorter searches.

this paper we justify the design assumption of simultaneous starts. Specifically, we provide algorithms to solve the associated synchronization problem, which we call the distributed firing squad problem (abbreviated DFS). A distributed algorithm for the DFS problem has two properties: (I) if any correct processor receives a .message to start a DFS synchronization, then at some future time all cor- rect processors will "fire" (formally, enter a special state), and (2) the correct processors all fire at exactly the same step

We describe novel techniques for establishing improved upper and lower bounds for modal logics of programs: 1) We introduce hybrid tree automata. These automata seems to be doubly exponential more powerful than Rabin tree automata but their emptiness problem is only exponentially harder (nondeterministic exponential time vs. nondeterministic polynomial time). The satisfiability problem for several logics is reducible to the emptiness problem for hybrid tree automata. Using this reduction we show that the satisfiability problems for Streett's delta-PDL. Kozen's μ-calculus and Parikh's game logic are solvable in nondeterministic exponential time, and the satisfiability problem for Emerson and Halpern's CTL and Vardi and Wolper's process logic (YAPL) are solvable in nondeterministic doubly exponential time. 2) We encode Turing machine computations by Kripke structures where every state in the structure represents a single tape cell. This yields a deterministic doubly exponential time lower bound for CTL and YAPL. 3) For variants of CTL and YAPL that deal only with finite computations we prove completeness for deterministic doubly exponential time.

The theme of this paper is to investigate to what extent approximation, possibly together with randomization, can reduce the complexity of problems in Valiant’s class # P. In general, any function in # P can be approximated to within any constant factor by a function in the class $\Delta _3^p $ of the polynomial-time, hierarchy. Relative to a particular oracle, $\Delta _3^p $ cannot be replaced by $\Delta _2^p $ in this result. Another part of the paper introduces a model of random sampling where the size of a set X is estimated by checking, for various “sample sets” S, whether or not S intersects X For various classes of sample sets, upper and lower bounds on the number of samples required to estimate the size of X are discussed. This type of sampling is motivated by particular problems in # P such as computing the size of a backtrack search tree. In the case of backtrack search trees, a sample amounts to checking whether a certain path exists in the tree. One of the lower bounds suggests that such tests alone are not sufficient to give a polynomial-time approximation algorithm for this problem, even if the algorithm can randomize.

A general technique is described for solving certain NP-hard graph problems in time that is exponential in a parameter k defined as the maximum, over all nonseparable components C of the graph, of the number of edges that must be added to a tree to produce C; for a connected graph, k is no more than the number of edges of the graph minus the number of vertices plus one.The technique is illustrated in detail for the following facility location problem: Given a connected graph G(V, E) such that each edge has an associated positive integer length and given a positive integer r, place the minimum number of centers on points of the graph such that every point of the graph is within distance r from some center (a "point" is either a vertex or a point on some edge).An algorithm of time complexity O(I El. (6r) rkm) is given.A parallel implementation of the algorithm, with optimal speedup over the sequential version for a fairly wide range for the number of processors, is presented.

The purpose of this paper is to study reducibilities that can be computed by combinational logic networks of polynomial size and constant depth containing AND’s, OR’s and NOT’s, with no bound placed on the fan-in of AND-gates and OR-gates. Two such reducibilities are defined, and reductions and equivalences among several common problems such as parity, sorting, integer multiplication, graph connectivity, bipartite matching and network flow are given. Certain problems are shown to be complete, with respect to these reducibilities, in the complexity classes deterministic logarithmic space, nondeterministic logarithmic space, and deterministic polynomial time. New upper bounds on the size-depth (unbounded fan-in) circuit complexity of symmetric Boolean functions are established.

The classes of languages accepted by alternating pushdown automata, alternating stack automata, and alternating nonerasing stack automata, both with and without an auxiliary space bounded worktape, are characterized in terms of complexity classes defined by time bounded deterministic Turing machines. It is also shown that alternating 2-way finite state machines accept only regular languages.

A relationship is established between (i) parallel random-access machines that allow many processors to concurrently read from or write into a common memory including simultaneous reading or writing into the same memory location (CROW PRAM), and (ii) combinational logic circuits that contain AND’s, OR’s and NOT’s, with no bound placed on the fan-in of AND-gates and OR-gates. Parallel time and number of processors for CROW PRAM’s are shown to correspond respectively (and simultaneously) to depth and size for circuits, where the time-depth correspondence is to within a constant factor and the processors-size correspondence is to within a polynomial. By applying a recent result of Furst, Saxe and Sipser, we obtain the corollary that parity, integer multiplication, graph transitive closure and integer sorting cannot be computed in constant time by a CROW PRAM with a polynomial number of processors. This is the first nonconstant lower bound on the parallel time required to solve these problems by a CROW PRAM with a polynomial number of processors. We also state and outline the proof of a similar result, due to W. L. Ruzzo and M. Tompa, that relates time and processor bounds for CRCW PRAM’S to alternation and space bounds for alternating Turing machines.

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

There are several computational problems that can be formulated as problems of counting the number of objects having a certain property. Valiant [22] has introduced the class #P which includes a variety of counting problems such as counting the number of perfect matchings in a graph, computing the permanent of a matrix [22], finding the size of a backtrack search tree [14], and computing the probability that a network remains connected when links can fail with a certain probability [23].

A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed on the fan-in of gates. It is shown that these models can simulate one another with the number of processors preserved to within a polynomial and parallel time preserved to within a constant factor. Reducibilities that preserve the measure in this sense are defined and several reducibilities and equivalences among problems are given. New upper bounds on the (unbounded fan-in) circuit complexity of symmetric Boolean functions are proved.

We present the design of a dictionary machine that is suitable for VLSI implementation, and we discuss how to realize this implementation efficiently. The machine supports the operations of SEARCH, INSERT, DELETE, and EXTRACTMIN on an arbitrary ordered set. Each of these operations takes time O(log n), where n is the number of entries present when the operation is performed. Moreover, arbitrary sequences of these instructions can be pipelined through the machine at a constant rate (i.e., independent of n and the capacity of the machine). The time O(log n) is an improvement over previous VLSI designs of dictionary machines which require time O(log N) per operation, where N is the maximum number of keys that can be stored.

Alternation is a generalization of nondeterminism in which existential and universal quantitiers can alternate during the course of a computation, whereas in a nondeterministic computation there are only existential quantifiers.Alternating Turing machines are defined and shown to accept precisely the recursively enumerable sets.Complexity classes of languages accepted by time-(space-) bounded alternating Turing machines are characterized in terms of complexity classes of languages accepted by space-(time-) bounded deterministic Turing machines.In particular, alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to deterministic 'exponential time.Subrecursive quantifier hierarchies are defined in terms of time-or space-bounded alternating Tufing machines by bounding the number of alternations allowed during computations.Alternating finite-state automata are defined and shown to accept only regular languages, although, in general, 2 2 states are necessary and sufficient to simulate a k-state alternating finite automaton deterministically.Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata.

For a number of two-person combinatorial games, the problem of determining the outcome of optimal play from a given starting position (that is, of determining which player, if either, has a forced win) is shown to be complete in exponential time with respect to logspace-reducibility. As consequences of this property, it is shown that (1) any algorithm which determines the outcome of optimal play for one of these games must infinitely often use a number of steps which grows exponentially as a function of the size of the starting position given as input; and (2) these games are “universal games” in the sense that, if G denotes one of these games and R denotes any member of a large class of combinatorial games (including Chess, Go, and many other games of popular or mathematical interest), then the problem of determining the outcome of R is reducible in polynomial time to the problem of determining the outcome of G.

Given two finite sets of k-tuples whose component elements are drawn from an infinite totally ordered set, the problem of identifying the k-tuples which belong to both sets is considered. Attention is restricted to algorithms that perform pairwise comparisons on the component elements of the k-tuples. If the two sets have cardinalities m and n with $m \leqq n$ it is shown that, in the worst case, \[ (m + n) \cdot \log _2 m + (m + n - 1)k \] comparisons are sufficient and \[ \max ((m + n) \cdot \log _2 m - 2.9m,(m + n - 1)k) \] comparisons are necessary. Upper and lower bounds are also given for the number of comparisons required to recognize duplicate tuples in a sequence of tuples, and to determine the lexicographic order of a sequence of tuples. In all cases, the disparity between the upper and lower bounds is at most a factor of two asymptotically.

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements for the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well (fewer than 2 p storage locations need be set aside for storing arrays having p or fewer positions) and enjoy good access characteristics (expected access time is O (1), and worst-case access time is O (log log p ) for p - or fewer-position arrays). Moreover, at the cost of only a modest additive increase in access time, storage demands can be decreased to (1 + δ) p locations for arbitrary δ > 0.

We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete in polynomial time, and other games complete in exponential time. We also find that computability on a parallel processing machine is a rather rugged notion, and present two parallel processing models that are polynomially equivalent in their running times. We also show that while n-state alternating finite automata accept only regular sets that can be accepted by 22n-O(logn) state deterministic automata, alternating pushdown automata accept all languages accepted by Turing machines in deterministic exponential time.

@In this paper this question is generalized to the following question:Given a polynomial f(x) and an operator D that maps polynomials to sets of polynomials,Find a minimal cost straightline program that computes some h(x) e D(f(x)).

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely, hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements on the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well [fewer than 2p storage locations need be set aside for storing arrays having p or fewer positions] and enjoy good access characteristics [expected access time is 0(1), and worst-case access time is 0(log log p) for p- or fewer-position arrays]. Moreover, at the cost of only an additive increase in access time, storage demands can be decreased to (l+ε)p locations for arbitrary ε>0. In fact, if one will abide a more drastic degradation of access efficiency, one can lower storage demands to p+o(p) locations.

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of SIMPLE MAX CUT (MAX CUT with edge weights restricted to value 1), and, as a corollary, the completeness of the OPTIMAL LINEAR ARRANGEMENT problem. We then show that even if the domains of the NODE COVER and DIRECTED HAMILTONIAN PATH problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For GRAPH 3-COLORABILITY, NODE COVER, and UNDIRECTED HAMILTONIAN CIRCUIT, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.

Random access machines (RAMs) are usually defined to have registers that hold integers. While this captures in part the structure of a commercial computer, it overlooks an implementation-dependent feature of most binary oriented machines, namely their ability to operate bit by bit on the bit vectors used to represent integers. Typical operations are bit-wise Boolean operations (and, or, not, etc.) and shifts by an amount specified in some register. These operations are ideal for certain problems, such as dealing with sets represented as bit vectors, some parsing algorithms [4], propositional calculus theorem proving, and analysis of sorting networks. A RAM so implemented we shall call a vector machine.

A Turing machine multiplies on-line if it receives its inputs low order digits first and it produces the k-th output digit before reading in the (k+1)-st inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-bit binary numbers in time F(n) into an on-line method, and the new algorithm requires time only 0(F(n) log n). Applying this technique to the fast multiplication algorithm of Schonhage and Strassen gives an upper bound of 0(n (log n)2 log log n) for on-line multiplication of integers. Other applications are to the on-line problems of products of polynomials over a finite ring, recognition of palindromes, and multiplication by a constant.

The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E)2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions.

We present algorithms which use only $O(\sqrt n )$ nonscalar multiplications (i.e. multiplications involving “x” on both sides) to evaluate polynomials of degree n, and proofs that at least $\sqrt n $ are required. These results have practical application in the evaluation of matrix polynomials with scalar coefficients, since the “matrix $ \times $ matrix” multiplications are relatively expensive, and also in determining how many multiplications are needed for polynomials with rational coefficients, since multiplications by integers can in principle be replaced by several additions.