The goal of this work is to show that if a minimal-time solution exists for a fundamental computation primitive, synchronizing networks of finite-state processors (formally known as the firing squad synchronization problems for directed and undirected networks), then there must exist „extraordinarily fast” algorithms for exactly solving the diameter problem in the standard RAM model of computation. These results can therefore be interpreted either as evidence that such minimal-time solutions for synchronization do not exist or as a potentially major algorithmic leap forward in the study of the diameter problem. We conjecture that the former is true. These results essentially complete the program outlined in [K. Kobayashi, Theoret. Comput. Sci., 259 (2001), pp. 129--143] to show that there exist a wide range of natural topologies for which it seems highly unlikely that there exist minimal-time solutions.

We show that if a minimal-time solution to a fundamental distributed computation primitive, synchronizing a network path of finite-state processors, exists on the three-dimensional, undirected grid, then we can conclude the purely complexity-theoretic result $P = NP$. Every previous result on network synchronization for various network topologies either demonstrates the existence of fast synchronization solutions or proves that a synchronization solution cannot exist at all. To date, it is unknown whether there is a network topology for which there exists a synchronization solution but for which no minimal-time synchronization solution exists. Under the assumption that $P \neq NP$, this paper solves this longstanding open problem in the affirmative.

A function h(w) is said to be useful for the coding theorem if the coding theorem remains to be true when the lengths |w| of codewords w in it are replaced with h(w). For a codeword w=a/sub 0/a/sub 1/...a/sub m-1/ of length m and an infinite sequence Q=(q/sub 0/, q/sub 1/, q/sub 2/, ...) of real numbers such that 0<q/sub n//spl les/ 1/2 , let |w|/sub Q/ denote the value /spl Sigma//sub n=0//sup m-1/ (if a/sub n/=0 then -log/sub 2/q/sub n/, else -log/sub 2/(1-q/sub n/)), that is, -log/sub 2/, (the probability that flippings of coins generate x) assuming that the (i+1)th coin generates a tail (or 0) with probability q/sub i/. It is known that if 0

The problem of deciding predicates concerned with m -tuples of words by means of 2-way multitape finite automata is considered. In general, more than m tapes are used to decide a predicate concerned with m -tuples of words. In such a way, a necessary and sufficient condition for a predicate to be decidable by a 2-way multitape finite automaton is obtained. The relation between the ability of Turing machines and that of 2-way multitape finite automata is also discussed.