1

この問題は、入力として 1 ビットを超える関数について説明したドイツ語問題の単純な一般化に関するものです。今回は、入力として 4 ビットの数値を取り、0 または 1 を出力するブール関数 f がありますf:{0,1}4→{0,1}。したがって、f への入力は、可能な 16 の 4 ビット 2 進数の 1 つです。

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

f は次の 2 つのタイプのいずれかであるとも言われています。

either f is a constant function, i.e., f(x) is the same for all 16 possible values of the input x, or
f is a balanced function, i.e., f(x) is 0 for exactly 8 of the possible 16 inputs and f(x) is 1 for the remaining 8 of the possible 16 inputs.

f の回路に入力 x を与え、出力 f(x) を観察することにより、f の回路を「ブラック ボックス」として使用することができます。これを「クエリ」操作と呼びます。

古典的な確率的アルゴリズムが、2 つのクエリを使用して、少なくとも 2/3 の確率で f が平衡または定数であるかどうかを判断できることを示します。

ヒント: (明らかに、決定論的アルゴリズムを使用してこれを行うことはできません。決定論的アルゴリズムが少なくとも 9 つの入力値の出力を確認しない限り、関数が平衡か定数かを調べる方法はありません)。

16 の可能な入力のセットから 2 つの入力を均一かつランダムに選択することを考えてみてください。最終的な結果は、これら 2 つのクエリの結果に確率的に依存する可能性があります。

4

2 に答える 2

0

編集:いくつかの確率を間違って計算していました。また、関数 f の 2 つの異なる入力をランダムに選択する必要があることも述べました。これは、f のバランスがとれている場合に、さまざまな結果が得られる確率を知ることができることを保証するためです。

関数が一定であるという事前確率が不明であるという事実は、アルゴリズムの成功確率を直接計算できないことを意味するため、この質問を難しくしています。ただし、この確率の境界を計算することはできます。

次の確率的アルゴリズムを提案します。

  • ランダムに 2 つの異なる 4 ビット値を選び、それぞれを関数 f に与えます。
  • 0,0 または 1,1 が見られる場合、確率 2/3 で「constant」を出力し、確率 1/3 で「balanced」を出力します。
  • それ以外の場合 (0,1 または 1,0 が表示される場合)、常に「バランスが取れている」と報告します。

実際に計算できるもの、つまり条件付き確率を見てみましょう。

  1. 「P(correct|constant) とは何ですか?つまり、f が定数である場合にアルゴリズムが正しい答えを返す確率は?」 f が一定の場合、アルゴリズムは 2/3 の確率で正しい答えを報告します。
  2. 「P(correct|balanced) とは何ですか?つまり、f が釣り合っている場合にアルゴリズムが正しい答えを返す確率です?」 f が釣り合っている場合、0,1 または 1,0 が表示される確率は 2*(8/16 * 8/15) = 8/15 であり、この場合、間違いなく正解が出力されます。残りの 7/15 のケース、つまり 0,0 または 1,1 が見られるケースでは、正解は 1/3 の確率で出力されるため、正しい出力の合計割合は 8/15 になります。 * 1 + 7/15 * 1/3 = 31/45 = 2/3 + 1/45 ≈ 0.6889.

ここで、関数が定数である事前確率が p であるとします。すると、アルゴリズムが正しい答えを出す確率は

pCorrect(p) = p*P(正しい|定数) + (1-p)*P(正しい|バランス)。

0 <= p <= 1 の場合、pCorrect(p) は少なくとも min(P(correct|constant), P(correct|balanced)) であり、最大で max(P(correct|constant), P(correct) |バランス)))。2/3 と 31/45 の最小値は 2/3 であるため、pCorrect は 2/3 で下から制限され、関数が一定である事前確率はすべて一定です。 (p を、各項をどれだけ含めるかを制御する「混合レバー」と考えると役立つ場合があります。p = 0 または p = 1 の場合、事実上、P(correct|balanced) または P(correct|constant )、それぞれ、p の中間値については、中間合計が得られます。)

于 2012-12-08T06:41:20.297 に答える
-1

さまざまなタイプの関数の確率を調べて、2つの指定された値に対してさまざまな結果を返します。

constant  0,0  50%
constant  1,1  50%
balanced  0,0  4/8 * 3/7 = 21,4%
balanced  0,1  4/8 * 4/7 = 28.6%
balanced  1,0  4/8 * 4/7 = 28.6%
balanced  1,1  4/8 * 3/7 = 21.4%

結果が0,0または1,1の場合、関数が一定である可能性は70％ですが、結果が0,1および1,0の場合、関数のバランスが取れている可能性は100％です。したがって、71.4％の確率で発生するケースは70％確実であり、28.6％の確率で発生するケースは100％確実です。平均して、78.6％の確信があります。

于 2012-12-08T05:06:09.283 に答える