كتب definition and variables
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
التعريف والمتغيرات (معلومة)
رسميا، تعتبر خوارزمية اختبار الخاصية ذات تعقيد استفسار q(n) ومعامل قرب ε لمشكلة قرار L كـ خوارزميةعشوائية حيث، عند مدخل x (كمثال على L) ينتج عن q(|x|) لـ x وتتصرف على النحو التالي :
- إذا كانت x في L، تتقبل الخوارزمية x باحتمالية ⅔.
- إذا كانت x تبعد عن L مسافة ε، سترفض الخوارزمية x باحتمالية ⅔.
وتعني " x تبعد عن L مسافة ε" أن مسافة هامنج بين x وأي خط على L يبعد على الأقل |x| ε. ويقال أن خوارزمية اختبار الخاصية لها خطأ من جانب واحد إذا استوفى الشرط الأقوى عند قبول احتمالية حالات x ∈ L هو 1 بدلا من ⅔. ويقال أن خوارزمية اختبار الخاصية غير قابلة للتكيف إذا كانت تنفذ جميع الاستفسارات قبل أن "تلاحظ" أي إجابات على الاستفسارات السابقة. ومثل هذه الخوارزمية يمكن رؤيتها على أنها تعمل على النحو التالي. أولا تتلقى الخوارزمية مدخلاتها. وقبل النظر إلى المدخلات، وذلك باستخدام العشوائية الداخلية، تقرر الخوارزمية أي رموز يُستفسر عنها. ثم، تلاحظ الخوارزمية هذه الرموز. وأخيرا، وبدون إجراء أية استفسارات إضافية (ولكن ربما باستخدام العشوائية الخاصة بها)، تقرر الخوارزمية ما إذا كانت تقبل أو ترفض الإدخال.
