Horn functions are Boolean functions where each of the prime implicants contains at most one negative literal. A class of Boolean functions is considered in this letter where a single term containing two negative literals is added by logical-or operation to a Horn function. We show that the function does not have any prime implicant containing three negative literals. We also show that if two terms containing two negative literals are added to a Horn function, then it may have many prime implicants all of which contain three negative literals. We show that it is P-complete to determine whether a given Boolean function in disjunctive normal form of the considered class is a tautology.

The minimum number of comparators in a (6,6)-merging network is shown to be 17. The number has been known to be either 16 or 17 [See Knuth, The Art of Computer Programming Vol. 3: Sorting and Searching, p. 230]. Minimum numbers for (n,n)-merging netwerks, 1 n 9, n 6, were already known. The problem had been open for more than two decades.

We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.

This paper deals with a popular puzzle known as Hi-Q. The puzzle is generalized: the board is extended to the size nn, an initial position of the puzzle is given, and a place is given on which only one token is finally placed. The complexity of the generalized Hi-Q is proved NP-complete.

ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk n) [S. A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. Contr. vol. 64]. We consider a game played by two persons: each player alternately moves a marker along an edge of a given digraph, and the first palyer who cannot move loses the game. It is shown that the problem to determine whether the first player can win the game on a digraph with n nodes exactly after logk n moves is complete for ACk nuder NC1 reducibility.

Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

Some graph theoretic problems are considered and these problems are proved to be complete for nondeterministic log-space. These graph problems concern matching, connectivity, feedback node set, diameter, radius and so on. A consideration is also mode in connection with the Jones' open problem.