照山 順一

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

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 時間で解く多項式領域アルゴリズムを与える.p...

本稿ではk集合整列問題に対して効率のよいアルゴリズムを与える.k集合整列問題とは以下のような問題である:n個のビンにk個のボールが入っており,i番目のビンにあるボールすべてに番号n-i+1がついている.隣り合うビンに存在する任意の2つのボールの交換のみを許した時,すべてのボールとビンの番号を一致させるためには何回の交換が必要だろうか.我々はこの問題に対して,高々(k+1)/4n^2+O(n)回の交換で本問題を解く貪欲アルゴリズムを与える.この値はn,kが大きくなるにつれて下界値と近くなる....

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...