نظام إثبات تفاعلي

في نظرية التعقيد الحسابي ، نظام الإثبات التفاعلي هو آلة مجردة تنمذج الحوسبة على أنها تبادل رسائل بين طرفين: مُثبت ومُتحقق . يتفاعل الطرفان من خلال تبادل الرسائل من أجل التأكد مما إذا كانت سلسلة معينة تنتمي إلى لغة أم لا. يُفترض أن المُثبت يمتلك موارد حسابية غير محدودة ولكن لا يمكن الوثوق به، في حين أن المُتحقق لديه قوة حسابية محدودة ولكن يُفترض أنه صادق دائمًا. يتم إرسال الرسائل بين المُثبت والمُثبت حتى يكون لدى المُثبت إجابة على المشكلة ويكون قد "أقنع" نفسه بأنها صحيحة.

جميع أنظمة الإثبات التفاعلية لها متطلبان:

• الاكتمال : إذا كانت العبارة صحيحة، فإن المُثبت الصادق (أي الذي يتبع البروتوكول بشكل صحيح) يمكنه إقناع المُتحقق الصادق بأنها صحيحة بالفعل.
• السلامة : إذا كانت العبارة خاطئة، فلا يمكن لأي مُثبت، حتى لو لم يتبع البروتوكول، أن يقنع المُحقق الصادق بأنها صحيحة، إلا مع وجود احتمالية صغيرة .

تعتمد الطبيعة المحددة للنظام، وبالتالي فئة تعقيد اللغات التي يمكنه التعرف عليها، على نوع الحدود الموضوعة على المُتحقق، بالإضافة إلى القدرات المُعطاة له - على سبيل المثال، تعتمد معظم أنظمة الإثبات التفاعلية بشكل حاسم على قدرة المُتحقق على اتخاذ خيارات عشوائية. كما تعتمد أيضًا على طبيعة الرسائل المتبادلة - كم عددها وما يمكن أن تحتويه. وقد وجد أن أنظمة الإثبات التفاعلية لها بعض الآثار المهمة على فئات التعقيد التقليدية المحددة باستخدام جهاز واحد فقط. فئات التعقيد الرئيسية التي تصف أنظمة الإثبات التفاعلية هي AM و IP .

كل نظام إثبات تفاعلي يحدد لغة رسمية للسلاسل . يشير مصطلح سلامة نظام الإثبات إلى الخاصية التي لا يمكن لأي مُثبت أن يجعل المُتحقق يقبلها على أنها عبارة خاطئة إلا باحتمالية ضئيلة. يُشار إلى الحد الأعلى لهذا الاحتمال باسم خطأ سلامة نظام الإثبات. بشكل أكثر رسمية، لكل مُثبت ، ولكل : ${\displaystyle L}$${\displaystyle y\not \in L}$${\displaystyle ({\tilde {\mathcal {P}}})}$${\displaystyle y\not \in L}$

${\displaystyle \Pr[(\perp ,({\text{accept}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon .}$

بالنسبة لبعض . طالما أن خطأ السلامة محدد بكسر متعدد الحدود لوقت التشغيل المحتمل للمحقق (أي )، فمن الممكن دائمًا تضخيم السلامة حتى يصبح خطأ السلامة دالة مهملة بالنسبة لوقت تشغيل المحقق. يتم تحقيق ذلك عن طريق تكرار الإثبات وقبول ما إذا كانت جميع البراهين صحيحة فقط. بعد التكرارات، سيتم تقليل خطأ السلامة إلى . ^[1]${\displaystyle \epsilon \ll 1}$${\displaystyle \epsilon \leq 1/\mathrm {poly} (|y|)}$${\displaystyle \ell }$${\displaystyle \epsilon }$${\displaystyle \epsilon ^{\ell }}$

يمكن اعتبار فئة التعقيد NP نظام إثبات بسيط للغاية. في هذا النظام، يكون المُتحقق عبارة عن آلة زمنية حتمية متعددة الحدود ( آلة P ). البروتوكول هو:

• ينظر المُثبت إلى المدخلات ويحسب الحل باستخدام قوته غير المحدودة ويعيد شهادة إثبات بحجم متعدد الحدود.
• يتحقق المُتحقق من صحة الشهادة في وقت محدد متعدد الحدود. إذا كانت صالحة، فإنه يقبلها؛ وإلا فإنه يرفضها.

في حالة وجود شهادة إثبات صالحة، يكون المُثبت قادرًا دائمًا على جعل المُتحقق يقبلها من خلال إعطائه تلك الشهادة. ولكن في حالة عدم وجود شهادة إثبات صالحة، فإن الإدخال ليس باللغة، ولا يمكن لأي مُثبت، مهما كان خبيثًا، إقناع المُتحقق بخلاف ذلك، لأن أي شهادة إثبات سيتم رفضها.

على الرغم من أنه قد يُنظر إلى NP على أنه يستخدم التفاعل، إلا أنه لم يتم تصور مفهوم الحساب من خلال التفاعل (في سياق نظرية التعقيد) حتى عام 1985 من قبل مجموعتين مستقلتين من الباحثين. النهج الأول، من قبل لازلو باباي ، الذي نشر "تداول نظرية المجموعة للعشوائية"، ^[2] حدد التسلسل الهرمي لفئة آرثر-ميرلين ( AM ). في هذا العرض التقديمي، آرثر (المحقق) هو آلة زمنية احتمالية متعددة الحدود، بينما يمتلك ميرلين (المثبت) موارد غير محدودة.

إن فئة MA على وجه الخصوص عبارة عن تعميم بسيط للتفاعل NP أعلاه حيث يكون المُتحقق احتماليًا بدلاً من حتميًا. بالإضافة إلى ذلك، بدلاً من مطالبة المُتحقق دائمًا بقبول الشهادات الصالحة ورفض الشهادات غير الصالحة، يكون أكثر تساهلاً:

• الاكتمال: إذا كانت السلسلة موجودة في اللغة، فيجب أن يكون المُثبت قادرًا على إعطاء شهادة بحيث يقبلها المُتحقق باحتمالية لا تقل عن 2/3 (اعتمادًا على الاختيارات العشوائية للمُتحقق).
• السلامة: إذا لم تكن السلسلة موجودة في اللغة، فلن يتمكن أي مُثبت، مهما كان خبيثًا، من إقناع المُتحقق بقبول السلسلة باحتمالية تتجاوز 1/3.

من المحتمل أن تكون هذه الآلة أقوى من بروتوكول تفاعل NP العادي ، كما أن الشهادات ليست أقل عملية للتحقق، حيث تعتبر خوارزميات BPP بمثابة حساب عملي تجريدي (انظر BPP ).

في بروتوكول العملة العامة ، تصبح الاختيارات العشوائية التي يتخذها المُتحقق عامة. وتظل خاصة في بروتوكول العملة الخاصة.

في نفس المؤتمر الذي حدد فيه باباي نظام الإثبات الخاص به لـ MA ، نشر شافي جولدواسر وسيلفيو ميكالي وتشارلز راكوف ^[3] ورقة بحثية تحدد نظام الإثبات التفاعلي IP [ f ( n )]. يحتوي هذا على نفس الآلات مثل بروتوكول MA ، باستثناء أن جولات f ( n ) مسموح بها لإدخال بحجم n . في كل جولة، يقوم المُتحقق بإجراء عملية حسابية ويمرر رسالة إلى المُثبت، ويقوم المُثبت بإجراء عملية حسابية ويمرر المعلومات مرة أخرى إلى المُتحقق. في النهاية يجب على المُتحقق اتخاذ قراره. على سبيل المثال، في بروتوكول IP [3]، سيكون التسلسل هو VPVPVPV، حيث V هو دورة المُتحقق و P هو دورة المُثبت.

في بروتوكولات آرثر-ميرلين، عرّف باباي فئة مشابهة AM [ f ( n )] والتي سمحت بجولات f ( n )، لكنه وضع شرطًا إضافيًا واحدًا على الآلة: يجب على المُتحقق أن يُظهر للمُثبت جميع البتات العشوائية التي يستخدمها في حسابه. والنتيجة هي أن المُتحقق لا يمكنه "إخفاء" أي شيء عن المُثبت، لأن المُثبت قوي بما يكفي لمحاكاة كل ما يفعله المُتحقق إذا كان يعرف البتات العشوائية التي استخدمها. يُطلق على هذا بروتوكول العملة العامة ، لأن البتات العشوائية ("رمي العملة") مرئية لكلا الجهازين. يُطلق على نهج IP بروتوكول العملة الخاصة على النقيض من ذلك.

المشكلة الأساسية في العملات العامة هي أنه إذا رغب المُثبت في إقناع المُتحقق بشكل خبيث بقبول سلسلة غير موجودة في اللغة، فيبدو أن المُتحقق قد يكون قادرًا على إحباط خططه إذا كان قادرًا على إخفاء حالته الداخلية عنه. كان هذا الدافع الأساسي في تحديد أنظمة إثبات الملكية الفكرية .

في عام 1986، أظهر جولدواسر وسيبسر [ ^4] ، ربما بشكل مفاجئ، أن قدرة المُتحقق على إخفاء رميات العملة عن المُثبت لا تفيده كثيرًا بعد كل شيء، حيث يمكن لبروتوكول العملة العامة آرثر-ميرلين الذي يحتوي على جولتين فقط التعرف على جميع اللغات نفسها. والنتيجة هي أن بروتوكولات العملة العامة والعملة الخاصة متكافئة تقريبًا. في الواقع، كما يوضح باباي في عام 1988، فإن AM [ k ] = AM لجميع الثوابت k ، وبالتالي فإن IP [ k ] ليس له أي ميزة على AM . ^[5]

لإثبات قوة هذه الفئات، ضع في اعتبارك مشكلة تماثل الرسم البياني ، وهي مشكلة تحديد ما إذا كان من الممكن تبديل رؤوس رسم بياني واحد بحيث يكون مطابقًا لرسم بياني آخر. هذه المشكلة موجودة في NP ، لأن شهادة الإثبات هي التبديل الذي يجعل الرسوم البيانية متساوية. اتضح أن مكمل مشكلة تماثل الرسم البياني، وهي مشكلة مشتركة بين NP وغير معروفة بأنها في NP ، لها خوارزمية AM وأفضل طريقة لرؤيتها هي من خلال خوارزمية عملات خاصة. ^[6]

قد لا تكون العملات الخاصة مفيدة، ولكن المزيد من جولات التفاعل مفيدة. إذا سمحنا لآلة التحقق الاحتمالي والمثبت القوي بالتفاعل لعدد متعدد الحدود من الجولات، فسنحصل على فئة من المشكلات تسمى IP . في عام 1992، كشف آدي شامير في إحدى النتائج المركزية لنظرية التعقيد أن IP يساوي PSPACE ، وهي فئة المشكلات التي يمكن حلها بواسطة آلة تورينج حتمية عادية في فضاء متعدد الحدود. ^[7]

إذا سمحنا لعناصر النظام باستخدام الحوسبة الكمومية ، فإن النظام يسمى نظام إثبات تفاعلي كمي ، وتسمى فئة التعقيد المقابلة QIP . ^[8] توجت سلسلة من النتائج باختراق عام 2010 وهو أن QIP = PSPACE . ^{[9] [10]}

لا تستطيع أنظمة الإثبات التفاعلية حل المشكلات التي لا يُعتقد أنها في NP فحسب ، ولكن تحت افتراضات حول وجود وظائف أحادية الاتجاه ، يمكن للمثبت إقناع المُتحقق بالحل دون إعطاء المُتحقق معلومات حول الحل على الإطلاق. هذا مهم عندما لا يمكن الوثوق بالمُتحقق بالحل الكامل. في البداية يبدو من المستحيل إقناع المُتحقق بوجود حل عندما لم ير المُتحقق شهادة، ولكن يُعتقد في الواقع أن مثل هذه الإثباتات، المعروفة باسم إثباتات المعرفة الصفرية، موجودة لجميع المشكلات في NP وهي قيمة في التشفير . تم ذكر إثباتات المعرفة الصفرية لأول مرة في الورقة الأصلية لعام 1985 حول IP بواسطة Goldwasser و Micali و Rackoff للغات نظرية الأعداد المحددة. ومع ذلك، أظهر Oded Goldreich و Silvio Micali و Avi Wigderson مدى قوتها . ^[6] لجميع NP ، وقد تم توسيع هذا لأول مرة بواسطة Russell Impagliazzo و Moti Yung لجميع IP . ^[11]

كان أحد أهداف مصممي بروتوكول الإنترنت هو إنشاء أقوى نظام إثبات تفاعلي ممكن، وفي البداية يبدو أنه لا يمكن جعله أكثر قوة دون جعل المُتحقق أكثر قوة وغير عملي. تغلب جولدواسر وآخرون على هذا في كتابهم "الأدلة التفاعلية متعددة المُثبتات: كيفية إزالة افتراضات صعوبة الإثبات" لعام 1988، والذي يحدد نوعًا مختلفًا من بروتوكول الإنترنت يسمى MIP حيث يوجد مُثبتان مستقلان . ^[12] لا يمكن للمُثبتين التواصل بمجرد أن يبدأ المُتحقق في إرسال الرسائل إليهما. تمامًا كما يسهل معرفة ما إذا كان المجرم يكذب إذا تم استجوابه هو وشريكه في غرف منفصلة، ​​فمن الأسهل بكثير اكتشاف مُثبت خبيث يحاول خداع المُتحقق لقبول سلسلة ليست في اللغة إذا كان هناك مُثبت آخر يمكنه التحقق منه مرتين.

في الواقع، كان هذا مفيدًا جدًا لدرجة أن باباي وفورتنو ولوند تمكنوا من إظهار أن MIP = NEXPTIME ، وهي فئة جميع المشكلات التي يمكن حلها بواسطة آلة غير حتمية في وقت أسي ، وهي فئة كبيرة جدًا. ^[13] يحتوي NEXPTIME على PSPACE، ويُعتقد أنه يحتوي بدقة على PSPACE. إن إضافة عدد ثابت من المثبتات الإضافية يتجاوز اثنين لا يمكّن من التعرف على أي لغات أخرى. مهدت هذه النتيجة الطريق لنظرية PCP الشهيرة ، والتي يمكن اعتبارها نسخة "مصغرة" من هذه النظرية.

يتمتع بروتوكول MIP أيضًا بالخاصية المفيدة المتمثلة في أنه يمكن وصف أدلة المعرفة الصفرية لكل لغة في NP دون افتراض الوظائف أحادية الاتجاه التي يجب أن يقوم بها بروتوكول IP . وهذا له تأثير على تصميم خوارزميات التشفير التي لا يمكن إثباتها. ^[12] علاوة على ذلك، يمكن لبروتوكول MIP التعرف على جميع اللغات في بروتوكول IP في عدد ثابت فقط من الجولات، وإذا تمت إضافة مُثبت ثالث، فيمكنه التعرف على جميع اللغات في NEXPTIME في عدد ثابت من الجولات، مما يُظهر مرة أخرى قوته على بروتوكول IP .

من المعروف أنه بالنسبة لأي ثابت k ، يمكن تحويل نظام MIP الذي يحتوي على k من أدوات الإثبات وعدد كبير من الجولات إلى نظام مكافئ يحتوي على 2 من أدوات الإثبات فقط وعدد ثابت من الجولات. ^[14]

بينما نظر مصممو IP في تعميمات أنظمة الإثبات التفاعلية الخاصة بباباي، نظر آخرون في القيود. نظام الإثبات التفاعلي المفيد للغاية هو PCP ( f ( n )، g ( n ))، وهو قيد على MA حيث لا يمكن لـ Arthur استخدام سوى f ( n ) بت عشوائي ولا يمكنه فحص سوى g ( n ) بت من شهادة الإثبات المرسلة بواسطة Merlin (باستخدام الوصول العشوائي في الأساس ).

هناك عدد من النتائج التي يسهل إثباتها حول فئات PCP المختلفة . ⁠ ⁠${\displaystyle {\mathsf {PCP}}(0,{\mathsf {متعدد}})}$ ، فئة آلات الوقت متعدد الحدود التي لا تحتوي على عشوائية ولكنها تتمتع بالوصول إلى شهادة، هي NP فقط . ⁠ ⁠${\displaystyle {\mathsf {PCP}}({\mathsf {متعدد}},0)}$ ، فئة آلات الوقت متعدد الحدود التي تتمتع بالوصول إلى عدد كبير جدًا من البتات العشوائية هي co- RP . كانت النتيجة الرئيسية الأولى لأرورا وصفرا هي أنه ⁠ ⁠${\displaystyle {\mathsf {PCP}}(\log ,\log )={\mathsf {NP}}}$ ؛ بعبارة أخرى، إذا تم تقييد المُتحقق في بروتوكول NP باختيار بتات شهادة الإثبات فقط للنظر فيها${\displaystyle O(\log n)}$ ، فلن يحدث هذا أي فرق طالما أنه يحتوي على بتات عشوائية${\displaystyle O(\log n)}$ لاستخدامها. ^[15]

علاوة على ذلك، تؤكد نظرية PCP أن عدد مرات الوصول إلى الإثبات يمكن تقليصه إلى ثابت. أي، ⁠ ⁠${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}(\log ,O(1))}$ . ^[16] لقد استخدموا هذا التوصيف القيم لـ NP لإثبات أن خوارزميات التقريب غير موجودة لإصدارات التحسين لبعض مشاكل NP-complete ما لم يكن P = NP . تتم دراسة مثل هذه المشاكل الآن في المجال المعروف باسم صعوبة التقريب .

• آلة أوراكل
• إثبات المعرفة

• أرورا، سانجيف؛ باراك، بواز، "نظرية التعقيد: نهج حديث"، مطبعة جامعة كامبريدج، مارس 2009.
• مايكل سيبسر (1997). مقدمة إلى نظرية الحوسبة . دار نشر PWS. رقم ISBN 978-0-534-94728-6.القسم 10.4: أنظمة الإثبات التفاعلية، ص 354-366.
• كريستوس باباديميتريو (1993). التعقيد الحسابي (الطبعة الأولى). أديسون ويسلي. رقم ISBN 978-0-201-53082-7.القسم 19.2: الألعاب ضد الطبيعة والبروتوكولات التفاعلية، ص 469-480.

• دكستر كوزين. البراهين التفاعلية. ملاحظات محاضرات CS682، ربيع 2004. قسم علوم الكمبيوتر، جامعة كورنيل.
• حديقة الحيوان المعقدة :
  • ماجستير، ماجستير، ماجستير في الخبرة، ماجستير في الهندسة
  • AM، AMEXP، AM تتقاطع مع co-AM، AM[polylog]، coAM، BP•NP
  • QMA، QMA+، QMA(2)، QMAlog، QMAM
  • IP، MIP، IPP، QIP، QIP(2)، compIP، frIP
  • PCP(r(n)،q(n))
• لاري جونيك. "هل الدليل إيجابي؟". شريط هزلي عن أنظمة الإثبات التفاعلية.