Junichi Teruyama

k-IBDD は,k 段のレイヤーを持つ分岐プログラムであり,各レイヤーが OBDD (順序付き二分決定図) となっている.本稿では,k-IBDD 充足可能性問題 (以下,k-IBDD SAT) を考える.k-IBDD SAT とは,入力として k-IBDD が与えられ,シンク 1 に到達する変数への割当が存在するかどうかを判定する問題である.本稿では,n 変数,poly(n) ノードの 2-IBDD SAT を高々 poly(n)・2n-√n 時間で解く多項式領域アルゴリズムを与える.poly(n) は n の多項式を表す.さらに,このアルゴリズムを拡張することにより,n 変数,poly(n) ノードの k-IBDD SAT を高々,poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムを与える.

We give efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows: We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. How many swaps are needed to move all balls to the same numbered bins. For this problem, we design an efficient greedy algorithm with (k+1)/4n^2+O(kn) swaps. As k and n increase, this approaches the lower bound of [numerical formula]. In addition, we design a more efficient recursive algorithm using (15)/(16)n^2+O(n) swaps for the k=3 case.

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most 3/4 N + o(N) queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove that any bounded-error quantum algorithm needs Ω(N/log^2N ) queries. For this, we introduce another query model and obtain a lower bound for this model with the adversary method, from which bound we get the desired lower bound in the original query model.

We investigate the following sorting puzzle: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n-i+1. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost (4n^2)/5 swaps. In this paper, we show an algorithm which solves this puzzle using less than (2n^2)/3 swaps. Since it is known that the lower bound of the number of swaps is [numerical formula],our result is almost tight. Futhermore, we show that for n=2^k+1(k〓0) the algorithm is optimal.