مرجع
آخر الزيارات

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

1٬937 كلمة•0 مشاهدة•🗒️ منذ 18 يوماً
باختصار: في نظرية التعقيد الحسابي نظام الإثبات التفاعلي هو نموذج حاسوبي مجرد يصف تبادل الرسائل بين طرفين: المُثبت (بموارد حسابية غير محدودة وغير موثوق به) والمُتحقق (بموارد حسابية محدودة وصادق دائماً). تجد هنا «ميب»، «كيو آي بي» و«بروتوكول العملات العامة مقابل بروتوكول العملات الخاصة» ضمن 10 أقسام.
المحتويات
  1. ميب
  2. كيو آي بي
  3. بروتوكول العملات العامة مقابل بروتوكول العملات الخاصة
  4. الكتب المدرسية
  5. ن ب
  6. خلفية
  7. عنوان IP
  8. بروتوكولات آرثر-ميرلين وميرلين-آرثر
  9. في سي بي
  10. لا يوجد معرفة
نظام الإثبات التفاعلي

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

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

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

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

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

ميب

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

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

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

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

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

كيو آي بي

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

بروتوكول العملات العامة مقابل بروتوكول العملات الخاصة

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

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

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

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

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

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

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

ومن ناحية أخرى، أرورا، سانجيف؛ باراك، بواز، "نظرية التعقيد: نهج حديث" ، مطبعة جامعة كامبريدج، مارس 2009.

وفي هذا الصدد، القسم 19.2: الألعاب ضد الطبيعة والبروتوكولات التفاعلية، ص. 469 – 480.

القسم 10.4: أنظمة الإثبات التفاعلية، ص. 354 – 366.

ن ب

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

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

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

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

خلفية

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

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

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

عنوان IP

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

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

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

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

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

وفي السياق ذاته، السلامة: إذا لم تكن السلسلة موجودة في اللغة، فلن يتمكن أي مُثبت، مهما كان خبيثًا، من إقناع المُتحقق بقبول السلسلة باحتمال يتجاوز 1/3.

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

في سي بي

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

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

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

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

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

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

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

لا يوجد معرفة

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.