آرثر مارلين البروتوكول

Question

تعلمت مؤخرا عن آرثر مارلين البروتوكول حددنا تعقيد الطبقات $انا,MA$.

وقد رأينا أيضا أن هناك نظرية تفيد بأن $AMAMAM...أنا=أنا$, ومع ذلك ليس لدينا محددة رسميا ، $AMAMAMAM...أنا$.

نحن لم إعطاء تعريف موجز عن أنها البروتوكول ، ولكن أود أن نرى تعريف رسمي دون بروتوكولات, مثل $أنا$ و $MA$ (و $مام$)

تعريف $AMA$ ينبغي أن يكون كافيا بالنسبة لي, فقط للحصول على تعليق كيف ينبغي أن ننظر.

وذلك بفضل!

Answer 1

$AMA$ هو في الأساس 3-جولة تفاعلية دليل النظام حيث المدقق (آرثر) هو فقط المسموح لها بإرسال العشوائية إلى المعايرة القياسية (ميرلين).
أنا لم أر مثل هذا تعريف صريح حتى الآن, ولكن أعتقد أننا يمكن صياغة ذلك على النحو التالي.الجولة الأولى من أنا[3] يبدأ مع ميرلين إرسال رسالة $m_1$ إلى آرثر.في الجولة الثانية ، آرثر يرسل العشوائية $r$ إلى ميرلين التي تليها النهائية الجولة الثالثة التي ميرلين يرسل رسالة $m_2$.آرثر ثم تقرر قبول/رفض استخدام القطعية متعدد الحدود-الوقت متحقق $V$.

أعتقد أننا يمكن أن تحدد الفئة على النحو التالي.
التعريف: $L ∈ AMA$ إذا كان هناك بولي الوقت القطعية الخوارزمية $V$ مثل:

• إذا $x \in L \;(|x| = n)$ ثم $\موجود P.Pr_{r \في \{0,1\}^{p(n)}} \left( V(x, m_1 ، ص ، m_2) = 1 ight) \قه 2/3$ حيث $\;m_1 = P(x),\;m_2 = P(x, r)$
• إذا $x \لافي L \;(|x| = n)$ ثم $\forall P.Pr_{r \في \{0,1\}^{p(n)}} \left( V(x, m_1 ، ص ، m_2) = 1 ight) \لو 1/3$ حيث $\;m_1 = P(x),\;m_2 = P(x, r)$

ملاحظة المعايرة القياسية $P$ هي وظيفة $P:\{0,1\}^* ightarrow \{0,1\}^{q(n)}$, حيث $q(n)$ هو متعدد الحدود.

انظر:الحسابية Complxity قبل أرورا-باراك القسم 8.1.