หมายเหตุ: ที่นี่ฉันใช้ดัชนี $0,1,2$ และ $0,1$ แทน $1, 2, 3$ และ $1,2$.
เราต้องแสดง $3$ปัญหาการแยกแยะไม่ได้เทียบเท่ากับ $2$- แยกแยะไม่ได้ 1.
$2$-แยกไม่ออกง่ายกว่า $3$- แยกแยะไม่ออก
ก่อนอื่นให้พิจารณาว่ามีศัตรูอยู่ $\คณิตศาสตร์แคล{A}_3$ ต่อต้าน
$3$- ปัญหาการแยกแยะไม่ออกกับความได้เปรียบ $\epsilon$.
กำหนด $\mathcal{B}^{\mathcal{A}_3}_2$:
รับสามข้อความ $(m_0, m_1, m_2)$ จาก $\คณิตศาสตร์แคล{A}_3$
$x \xleftarrow{\$} \mathbb{Z}_3$
$(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$
ส่ง $(m^\prime_0, m^\prime_1)$ ต่อผู้ท้าชิงและรับ $ค$.
ส่ง $ค$ ถึง $\คณิตศาสตร์แคล{A}_3$ และรับ $ข$.
ถ้า $b=x$ จากนั้นส่งคืนบิตแบบสุ่ม $b^\ไพรม์$ อย่างอื่นกลับมา $(b- x \mod 3)$.
เรามาพิสูจน์กันก่อนว่า $\คณิตศาสตร์แคล{B}_2$ มีโอกาสที่จะชนะ $\frac{1-\epsilon}{4} +\epsilon$.
ให้โทร $b''$ บิตที่ผู้ท้าชิงเลือก
$\mathbb{P}(\mathcal{B}_2 ชนะ)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 ชนะ|
b- x \mod 3 = b'') +
\mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 ชนะ|
b- x \mod 3 \neq b'')$
$= \epsilon \cdot 1 + (1 - \epsilon)\mathbb{P}((b=x) \wedge b^\prime =b'' |
b- x \mod 3 \neq b^{\prime\prime}) $
$= \epsilon + (1 - \epsilon)\frac{1}{2}\cdot\frac{1}{2}.qed$
ตอนนี้เราสามารถดูข้อได้เปรียบ:
$|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.
ถ้า $|\frac{1}{3}- \epsilon|$ ไม่สำคัญก็หมายความว่า $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ ก็ไม่น้อยหน้าเช่นกัน
$3$-แยกไม่ออกง่ายกว่า $2$- แยกแยะไม่ออก
ตอนนี้ให้พิจารณาว่ามีศัตรูอยู่ $\คณิตศาสตร์แคล{A}_2$ ต่อต้าน
$2$- ปัญหาการแยกแยะไม่ออกกับความได้เปรียบ $\epsilon$.
กำหนด $\mathcal{B}^{\mathcal{A}_2}_3$:
รับสองข้อความ $(m_0, m_1)$จาก $\คณิตศาสตร์แคล{A}_2$
$b \xleftarrow{\$} \mathbb{Z}_2$
$m_2 := m_{b}$
ส่ง $(m_0, m_1, m_2)$ ต่อผู้ท้าชิงและรับ $ค$.
ส่ง $ค$ ถึง $\คณิตศาสตร์แคล{A}_2$ และรับ $b^\ไพรม์$.
$x \xleftarrow{\$} \big\{b, 2\big\}$
ถ้า $b^\prime=b$ จากนั้นส่งคืน x มิฉะนั้นส่งคืน $b^\ไพรม์$
เมื่อพิสูจน์ครั้งแรกคำนวณความน่าจะเป็นที่จะชนะ $\คณิตศาสตร์แคล{B}_3$.
$\mathbb{P}(\mathcal{B}_3 ชนะ) =
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ|b''=2) +
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ| b''=b)+
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ| b''=1 - b) $
$\mathbb{P}(\mathcal{B}_3 ชนะ) =
\frac{1}{3}\mathbb{P}(b'=b \wedge x=2|b''=2) +
\frac{1}{3}\mathbb{P}(b'=b \wedge x=b| b''=b)+
\frac{\epsilon}{3}.$
เพราะ $x$ ถูกเลือกโดยไม่ขึ้นกับ $ข'$:
$\mathbb{P}(\mathcal{B}_3 ชนะ)$
$= \frac{1}{3}\mathbb{P}(b'=b|b''=2) \cdot \mathbb{P}(x=2|b''=2) +
\frac{1}{3}\mathbb{P}(b'=b|b''=b') \cdot \mathbb{P}(x=b''|b''=b')+
\frac{\epsilon}{3} $
$\mathbb{P}(\mathcal{B}_3 ชนะ) =
\frac{1}{3}\epsilon \cdot \frac1 2 +
\frac{1}{3}\epsilon \cdot \frac1 2+
\frac{\epsilon}{3} = \frac{2\epsilon}{3}.$
ตอนนี้เราคำนวณความได้เปรียบของ $\คณิตศาสตร์แคล{B}_3$:
$|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$
ถ้า $|\frac{1}{2}- \epsilon|$ ไม่สำคัญก็หมายความว่า $|\frac{1}{3} - \frac{2\epsilon}{3}|$ ก็ไม่น้อยหน้าเช่นกัน
เราสรุปได้ว่าปัญหาเหล่านี้เทียบเท่ากัน