حساب العتبة والأمان التشفيري

آلات العتبة هي آلات تورينغ يتم تحديد قبولها وفقًا لأي جزء من مسارات حساب الآلة هو مسارات قبول. الآلات الاحتمالية هي آلات تورينغ يتم تحديد قبولها وفقًا لوزن الاحتمالية لمسارات الحساب المقبولة للآلة. في عام 1975، أثبت سيمون أنه بالنسبة لآلات الزمن المتعدد الحدود ذات خطأ غير محدد، فإن هذين المفهومين يعطيان نفس الفئة، PP\@. ربما لأن نتيجة سيمون بدت وكأنها تدمج بين وضع العتبة ووضع الحساب الاحتمالي، فإن العلاقة بين حساب العتبة والحساب الاحتمالي في حالة الخطأ المحدد لم يتم استكشافها. في هذه الورقة، نقارن بين فئة الاحتمالات ذات الخطأ المحدد BPP وبين الفئة المماثلة للعتبة، ، وأيضًا، بشكل عام، ندرس الخصائص الهيكلية لـ. نثبت أن BPP₏₀ₓ₇ تحتوي على كل من ^ و ^ NP وأن BPP₏₀ₓ₇ مُدرجة في ^{ ₂ᵖ}، BPP^NP، و PP\@. نخلص إلى أنه، ما لم ينهار التسلسل الهرمي المتعدد الحدود، فإن حساب العتبة ذو الخطأ المحدد أقوى بشكل صارم من حساب الاحتمال ذو الخطأ المحدد. ننظر أيضًا إلى المفهوم الطبيعي للوصول الآمن إلى قاعدة بيانات: يجب أن لا يحصل الخصم الذي يشاهد الاستفسارات على أي معلومات حول الإدخال سوى ربما طوله. نوضح لكل من و أنه إذا كانت هناك أي قاعدة بيانات تختلف فيها هذه الصياغة للأمان عن الأمان المقدم من الوصول إلى قاعدة البيانات غير المبالي، فإن \@. ومن ثم، إذا كانت هناك مجموعة تفتقر إلى دوائر صغيرة يمكن قبولها بأمان، فإن.