有向グラフのs-t接続問題に対するディスジョイントまたはインデクシングまたは内積問題の削減

I am asked to prove that an O(1)-pass randomized streaming
algorithm that solves s-t connectivity problem in a simple directed
graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility
$>frac{1}{2}$, has space lower bound of $Omega(n^2)$
bits
, using techniques in communication complexity theory.

問題は、有向グラフのs-t接続問題を、通信複雑性理論の確立されたスペースの下限を使っていくつかの問題に減らすことです。スペースの下限に基づいて、私は2つのブール値ベクトルの分離度インデックス、または内積つまり、アリス$(i、j)は$
n ^ 2長さのブール値ベクトル$ a $を持ち、$ a [i times k + j] = 1 $の長さ$ n ^ 2
$を持ちます。 E $です。このようにして、問題をs-t接続問題に還元することができれば、$ Omega(n ^ 2)$
boundを証明できます。

しかし、私は数日間考えてきましたが、ここからどのように前進するかについての手がかりはまだありません…私はいくつかのアイデアやヒントを大いに感謝します。

ベストアンサー

アリスが$ n $ビット列$ x_1x_2x_3 … x_n $を持ち、ボブが$ n
$のインデックスを持っている通信問題を考えてみましょう。ボブの目標は、$ x $のビット$ i $ $ 1 $かどうか。

この問題は、アリスが少なくとも$ n $ビットをボブに送信する必要があることが知られています。

今度は、$ x_i = 1 $の場合にのみ$ 3 $から$ s $までの長さのパスを持つグラフを作成します。

頂点集合$ V = s cupA cupB cupt $を考えてみましょう。ここで$ s $と$ t
$は単一ノードですが、$ A = {a_1、a_2、…、a_ sqrt {n} }、B =
{b_1、b_2、…、b_ sqrt {n} } $とエッジは$ E_ {alice} $と$ E_ {bob}
$を設定します。

ここで、$ f_ {l} [i] $はfの最初の要素を表し、$ f_ {l} [i] $は$ f_ { {r} [i]
$は2番目の要素を示します。

すべてのインデックス$ j $ where $ x_j = 1 $に対して、$ E_ {alice} $は$ a_ {f_l
[j]} $と$ b_ {f_r [j]} $の間にあります。 $ E_ {bob} $は$ s $と$ a_ {f_l [i]}
$の間に、また$ b_ {f_r [i]} $と$ t $の間にエッジがあります。

グラフ$ G =(V、E_ {alice} cup E_ {bob})$は、$ x_i = 1 $の場合にのみ長さ3の$ s
$から$ t $へのパスを持ちます。

これを直接接続にするために、頂点集合$ V $を取って、それをE_ {alice} cup内の$
V_0、V_1、V_2、V_3 $と各エッジ$(u、v)の4つのコピーに置き換えますE_ {bob} $と置き換えると、$ v_i
$は$ vに対応するノードに対応する$(u_i rightarrow v_ {i + 1})、i in {0,1,2 }
$ V $ in $ V_i $である。 $ s_0 $から$ t_3 $への(有向)パスがある場合に限り、$ x_i = 1
$となります。

ここでのノードの総数は$ 8 sqrt {n} + 8
$であるので、s-t接続のための任意の二次二次空間ストリーミングアルゴリズムは、INDEX問題のための準線形一方向通信プロトコルを意味するが、これは不可能である。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です