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

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

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

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

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

 خلفية 
يحدد كل نظام إثبات تفاعلي لغة رسمية للسلاسل (). تُعرف سلامة نظام الإثبات بالخاصية التي تمنع أي مُثبت من إقناع المُتحقق بقبول عبارة خاطئة (y∈/L)، إلا باحتمالية ضئيلة جداً. يُشار إلى الحد الأعلى لهذا الاحتمال بـ خطأ سلامة نظام الإثبات. وبشكل أكثر رسمية، لكل مُثبِّت  ولكل سلسلة  لا تنتمي إلى اللغة:



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

 فئات البراهين التفاعلية 

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

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

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

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

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

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

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

 بروتوكول العملات العامة مقابل بروتوكول العملات الخاصة 
في بروتوكول "العملة المعدنية العامة" (Public-Coin Protocol)، تُعلن الاختيارات العشوائية التي يجريها المُتحقق. في المقابل، تظل هذه الاختيارات خاصة ضمن بروتوكول "العملة المعدنية الخاصة" (Private-Coin Protocol).

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

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

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

في عام 1986، أظهر جولدواسر وسيبسر Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems . Proceedings of ACM STOC'86, pp. 58–68. 1986. ، بشكل مفاجئ ربما، أن قدرة المُتحقق على إخفاء رميات العملة عن المُثبت لا تُقدم له فائدة تُذكر. فقد تبين أن بروتوكول العملات العامة آرثر-ميرلين، الذي يتضمن جولتين فقط، قادر على تمييز جميع اللغات ذاتها. وبالتالي، فإن بروتوكولات العملة العامة والعملة الخاصة متكافئة تقريباً.وكما أوضح باباي في عام 1988، فإن AM[k]=AM لجميع الثوابت k، مما يعني أن IP[k] ليس له أي أفضلية على AM.

لإثبات قوة هذه الفئات، نأخذ في الاعتبار <b>مشكلة تماثل الرسم البياني</b>، التي تُعنى بتحديد ما إذا كان بالإمكان إعادة ترتيب رؤوس رسم بياني ليطابق رسماً بيانياً آخر. تقع هذه المشكلة ضمن فئة NP، حيث تمثل شهادة الإثبات التبديل الذي يجعل الرسوم البيانية متساوية. اتضح أن مُكمّل مشكلة تماثل الرسم البياني (مشكلة co-NPالتي لا يُعرف عنها أنها في NP) يمتلك خوارزمية AM،وأفضل طريقة لاستيعابها هي من خلال خوارزمية العملات المعدنية الخاصة.

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

 كيو آي بي 
إذا سمحنا لعناصر النظام باستخدام الحوسبة الكمومية، يُصبح اسمه نظام إثبات تفاعلي كمي، وتُدعى فئة التعقيد المقابلة QIP.  وقد توجت سلسلة من النتائج باكتشاف مهم في عام 2010، وهو أن QIP = PSPACE. .  

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

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

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

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

يستطيع بروتوكول MIP تمييز جميع اللغات في IP في عدد ثابت من الجولات فقط. وإذا أُضيف مُثبِّت ثالث، فإنه يمكنه التعرف على جميع اللغات في NEXPTIME خلال عدد ثابت من الجولات أيضاً، مما يؤكد مجدداً تفوقه على IP .

من المعروف أنه لأي ثابت k، يمكن تحويل نظام MIP الذي يحتوي على k مُثبِتات وعدد كبير من الجولات إلى نظام مكافئ له مُثبتان فقط وعدد ثابت من الجولات. 

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

هناك جملة من النتائج التي يسهل البرهان عليها فيما يخص فئات PCP المتنوعة. فعلى سبيل المثال:

 PCP(0, poly): تمثل هذه الفئة آلات الزمن متعددة الحدود التي تعمل بدون عشوائية ولكنها تتميز بقدرتها على الوصول إلى شهادة إثبات، وهي مكافئة تماماً لفئة NP.
 PCP(poly, 0): تصف هذه الفئة آلات الزمن متعددة الحدود التي يمكنها الاستفادة من عدد كبير جداً من البتات العشوائية، وهي تكافئ فئة co-RP.

أما النتيجة الجوهرية الأولى التي توصّل إليها أرورا وصفرا فهي: PCP(log, log) = NP. بعبارة أخرى، إذا كانت قدرة المُتحقق ضمن بروتوكول NP محدودة باختيار O(logn) بت عشوائي فقط، وبفحص O(logn) بت فقط من شهادة الإثبات للنظر فيها، فإن هذا التقييد لا يُحدث أي فرق في قوة الفئة، شريطة أن تظل البتات العشوائية المتاحة للاستخدام هي O(logn) بت، وأن تكون البتات المسموح بفحصها من الشهادة هي O(logn) بت أيضاً. [1]

علاوة على ذلك، تؤكد نظرية PCP إمكانية تقليص عدد مرات الوصول إلى الإثبات إلى حد ثابت. وهذا ما تعبر عنه المعادلة:  . وقد استُخدمت هذه الخاصية القيمة لفئة NP لإثبات أن خوارزميات التقريب غير موجودة لإصدارات التحسين لبعض مشاكل NP-complete، ما لم يكن P = NP. تُدرس الآن مثل هذه المشاكل ضمن المجال المعروف باسم <b>صلابة التقريب</b>.

 انظر أيضا 

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

 مراجع 

 الكتب المدرسية 

 أرورا، سانجيف؛ باراك، بواز، "نظرية التعقيد: نهج حديث" ، مطبعة جامعة كامبريدج، مارس 2009.
 القسم 10.4: أنظمة الإثبات التفاعلية، ص. 354 – 366.
 القسم 19.2: الألعاب ضد الطبيعة والبروتوكولات التفاعلية، ص. 469 – 480.

 روابط خارجية 

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

تصنيف:نظرية التعقيد الحسابي
تصنيف:صفحات بترجمات غير مراجعة