International Journal of Foundations of Computer Science

The log cost measure has been viewed as a more reasonable method of measuring the time complexity of an algorithm than the unit cost measure. The more widely used unit cost measure becomes unrealistic if the algorithm handles extremely large integers. Parallel machines have not been examined under the log cost measure. In this paper, we investigate the Parallel Random Access Machine under the log cost measure. Let the instruction set of a basic PRAM include addition, subtraction, and Boolean operations. We relate resource-bounded complexity classes of log cost PRAMs to complexity classes of Turing machines and circuits. We also relate log cost PRAMs with different instruction sets by simulations that are much more efficient than possible in the unit cost case. Let LCRCW^k(CRCW^k) denote the class of languages accepted by a log cost (unit cost) basic CRCW PRAM in O(log^k n) time with the polynomial in n number of processors. We position the log cost PRAM in the hierarchy of parallel complexity classes as: AC^k=CRCW^k⊆(NC^k+1, LCRCW^k+1)⊆AC^k+1=CRCW^k+1.

A simple algorithm is given to rebalance a binary search tree of optimal height after a single update. The algorithm uses time which is linear in the number of nodes. In comparison to previous algorithms it is short and very easy to implement. Moreover, this algorithm can be used to implement other classes of balanced trees and it is suitable for each update. When applied to perfectly balanced trees it has a lower average cost than previous algorithms.

The problem of nonpreemptively scheduling a set of n independent jobs with identical release times so as to minimize the number of late jobs is considered. It is known that the problem can be solved in O(n log n) time, by an algorithm due to Moore, for a single processor, and that it becomes NP-hard for two or more identical processors, even if all jobs have identical due dates. In this paper we give a fast heuristic, based on Moore’s algorithm, for the multiprocessor case. Like Moore’s algorithm, our heuristic also admits an O(n log n) implementation. It is shown that the performance ratio of the heuristic is 4/3 for two identical processors, where the performance ratio is defined to be the least upper bound of the ratio of the number of on-time jobs in an optimal schedule versus that in the schedule generated by the heuristic.

We define a subclass of Petri nets called m–state n–cycle Petri nets, each of which can be thought of as a ring of n bounded (by m states) Petri nets using n potentially unbounded places as joins. Let Ring(n, l, m) be the class of m–state n–cycle Petri nets in which the largest integer mentioned can be represented in l bits (when the standard binary encoding scheme is used). As it turns out, both the reachability problem and the boundedness problem can be decided in O(n(l+log m)) nondeterministic space. Our results provide a slight improvement over previous results for the so-called cyclic communicating finite state machines. We also compare and contrast our results with that of VASS(n, l, s), which represents the class of n-dimensional s-state vector addition systems with states where the largest integer mentioned can be described in l bits.

Given a rational matrix A, and a set of rational matrices B, C,… which commute with A, we give polynomial time algorithms to compute exactly the Jordan Normal Form of A, as well as the transformed matrices of B, C,…. We also obtain the transformation matrix and its inverse exactly in polynomial time.

Cai and Furst introduced the notion of bottleneck Turing machines. Based on Barrington’s innovating technique, which is used to showed that polynomial-size branching programs have exactly the same power as NC¹, Cai and Furst showed that the languages recognized by width-5 bottleneck Turing machines are exactly the same as those in PSPACE. In this paper, computational power of bottleneck Turing machines with widths fewer than 5 is investigated. It is shown that width-2 bottleneck Turing machines capture ⊕P//OptP, the class of sets recognized by ⊕P-machines with pre-computation in OptP. For languages recognized by bottleneck Turing machines with width-3 and width-4, some lower-bounds and upper-bounds are shown.

We continue the investigation of polynomial-time reducibilities along the directions of [8]. We show that there is a set which is f(n)-conjunctive (similarly f(n)-disjunctive) deterministic polynomial time reducible to a tally set but is not g(n)-conjunctive (respectively g(n)-disjunctive) deterministic polynomial time reducible to any sparse set. We also show that there is a set which is f(n)-conjunctive deterministic polynomial time reducible to a tally set but is not g(n)-turing non-deterministic polynomial time reducible to any tally set. Several interesting corollaries about the closure of sparse and tally sets under such reducibilities follow from these results.