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

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

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

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

على الرغم من إمكانية اعتبار فئة NP مستخدمة للتفاعل، إلا أن مفهوم الحوسبة من خلال التفاعل لم يتبلور (في سياق نظرية التعقيد) إلا في عام ١٩٨٥ على يد مجموعتين بحثيتين مستقلتين. إحدى هاتين المجموعتين، التي قدمها لازلو باباي في بحثه "استبدال نظرية الزمر بالعشوائية" ^{[ ٢ ]} ، عرّفت التسلسل الهرمي لفئات آرثر-ميرلين ( 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 ، لأن شهادة الإثبات هي التبديل الذي يجعل الرسمين البيانيين متساويين. وقد تبيّن أن مكمل مسألة تماثل الرسوم البيانية، وهي مسألة co- NP غير معروفة بانتمائها إلى فئة NP ، لها خوارزمية AM ، وأفضل طريقة لإثبات ذلك هي من خلال خوارزمية العملات الخاصة. ^{[ 6 ]}

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

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

لا تقتصر قدرة أنظمة الإثبات التفاعلية على حل المشكلات التي لا يُعتقد أنها تنتمي إلى فئة NP فحسب، بل يمكنها أيضًا، بافتراض وجود دوال أحادية الاتجاه ، إقناع المُثبت بالحل دون تزويده بأي معلومات عنه. وهذا أمر بالغ الأهمية عندما لا يُمكن الوثوق بالمُثبت في الحصول على الحل الكامل. قد يبدو للوهلة الأولى من المستحيل إقناع المُثبت بوجود حل دون الاطلاع على الشهادة، ولكن يُعتقد أن هذه البراهين، المعروفة ببراهين المعرفة الصفرية ، موجودة بالفعل لجميع المشكلات في فئة NP ، وهي ذات قيمة كبيرة في علم التشفير . ذُكرت براهين المعرفة الصفرية لأول مرة في الورقة البحثية الأصلية لعام 1985 حول IP من قِبل غولدواسير وميكالي وراكوف للغات نظرية الأعداد المحددة. ومع ذلك، فقد أظهر أوديد غولدرايش وسيلفيو ميكالي وآفي ويغدرسون مدى قوتها لجميع مشكلات NP ، ^{[ 6 ]} ثم قام راسل إمباغليازو وموتي يونغ بتوسيع نطاقها ليشمل جميع مشكلات IP . ^{[ 11 ]}

كان أحد أهداف مصممي بروتوكول الإثبات التفاعلي (IP) هو ابتكار أقوى نظام إثبات تفاعلي ممكن، ويبدو للوهلة الأولى أنه لا يمكن تعزيز قوته دون تعزيز قدرة المُدقِّق، مما يجعله غير عملي. وقد تغلب غولدواسير وزملاؤه على هذه المشكلة في بحثهم المنشور عام ١٩٨٨ بعنوان "الإثباتات التفاعلية متعددة المُثبتين: كيفية إزالة افتراضات عدم قابلية الحل"، والذي يُعرّف نوعًا مختلفًا من بروتوكول الإثبات التفاعلي يُسمى MIP ، حيث يوجد مُثبتان مستقلان. ^{[ ١٢ ]} لا يستطيع المُثبتان التواصل بمجرد أن يبدأ المُدقِّق بإرسال الرسائل إليهما. وكما أنه من الأسهل معرفة ما إذا كان المجرم يكذب إذا تم استجوابه هو وشريكه في غرفتين منفصلتين، فمن الأسهل بكثير اكتشاف مُثبت خبيث يحاول خداع المُدقِّق لقبول سلسلة نصية ليست ضمن اللغة إذا كان هناك مُثبت آخر يمكنه التحقق منه.

في الواقع، كان هذا مفيدًا للغاية لدرجة أن باباي وفورتنو ولوند تمكنوا من إثبات أن 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 حيث لا يستطيع آرثر استخدام سوى f ( n ) بت عشوائية، ولا يمكنه فحص سوى g ( n ) بت من شهادة الإثبات المرسلة من ميرلين (باستخدام الوصول العشوائي بشكل أساسي ).

هناك عدد من النتائج التي يسهل إثباتها حول فئات مختلفة من برامج الرعاية الصحية الأولية .${\displaystyle {\mathsf {PCP}}(0,{\mathsf {poly}})}$، فئة الآلات ذات الوقت متعدد الحدود التي لا تحتوي على عشوائية ولكنها تمتلك إمكانية الوصول إلى شهادة، هي ببساطة NP .${\displaystyle {\mathsf {PCP}}({\mathsf {poly}},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-كاملة إلا إذا ^كانت P = NP . تُدرس هذه المسائل الآن في مجال يُعرف بصعوبة التقريب .