اختبار الخاصية

في علوم الحاسوب، خوارزمية اختبار الخاصية لمشكلة قرار هي الخوارزمية التي يكون فيها تعقيد تساؤلها لمدخلاتها أصغر بكثير من حجم المشكلة. وعادة ما يتم استخدام خوارزميات اختبار الخاصية لتقرر ما إذا كان بعض الكينونات الرياضية (مثل رسم بياني أو وظيفة بولياني) لديها خاصية «عالمية»، أو أنها «بعيدة» عن امتلاك هذه الخاصية، وذلك باستخدام عدد قليل من التساؤلات «المحلية» للكائن. فعلى سبيل المثال، مشكلة الوعد التالية تُدخل خوارزمية تعقيد تساؤلها مستقل عن الحجم (لثابت تعسفي ε > 0):

"وبالنظر إلى الرسم البياني G على رؤوس n، قرر ما إذا كان G مخطط ثنائي، أواذا كان لا يصلح لـ G أن تكون مخطط ثنائي حتى بعد إزالة مجموعة فرعية تعسفية في الأكثر $\epsilon {\tbinom {n}{2}}$ من حواف G"

خوارزميات اختبار الخاصية مهمة في نظرية PCP.

التعريف والمتغيرات

رسميا، تعتبر خوارزمية اختبار الخاصية ذات تعقيد استفسار q(n) ومعامل قرب ε لمشكلة قرار L كـ خوارزميةعشوائية حيث، عند مدخل x (كمثال على L) ينتج عن q(|x|) لـ x وتتصرف على النحو التالي:

• إذا كانت x في L، تتقبل الخوارزمية x باحتمالية ⅔.
• إذا كانت x تبعد عن L مسافة ε، سترفض الخوارزمية x باحتمالية ⅔.

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

خصائص وحدود

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

وبعكس إعدادات التعقيدات النظرية الأخرى، يتأثر مقارب تعقيد التساؤل لخوارزميات اختبار الخاصية بشكل كبير بطريقة تمثيل الاقتراحات. فعلى سبيل المثال، عندما يكون ε= 0.01، تُدخِل مشكلة اختبار انقسام الرسوم البيانية المتراكمة (التي تمثلها المصفوفات المتصلة) خوارزمية ذات تعقيد تساؤل ثابت. وفي المقابل، تتطلب الرسوم البيانية المتناثره على القمم n (التي تمثلها قائمة متصلة) خوارزميات اختبار خاصية ذات تعقيد تساؤل $\Omega ({\sqrt {n}})$.

تعقيد التساؤل في خوارزميات اختبار الخاصية ينمو كلما صغر معامل التقارب ε لجميع الخصائص الغير عادية. وهذا الاعتماد على ε ضروري حيث أن التغيير في أقل من ε من الرموز في المدخلات لا يمكن الكشف عنه مع احتمال ثابت باستخدام عدد أقل من الاستعلامات O(1/ ε). ويمكن اختبار العديد من خصائص الرسوم البيانية الكثيفة المثيرة للاهتمام عن طريق استخدام تعقيد تساؤل يعتمد فقط على ε وليس على حجم الرسم البياني n. ومع ذلك، فيمكن أن تنمو تعقيد التساؤل بسرعة هائلة كوظيفة ε. وعلى سبيل المثال، كانت أفضل خوارزمية معروفة لوقت طويل لاختبار ما إذا كان الرسم البياني لا يحتوي على مثلث كان لديه تعقيد تساؤل والذي كان في شكل دالة برجية poly(1/ε)، وفقط في عام 2010 تم تحسينه إلى دالة برجية log(1/ε).

المراجع

• Dana Ron. Property Testing. In Handbook of Randomization, 2000. [1]
• Ronitt Rubinfeld. Sublinear-time Algorithms. In Proceedings of the 2006 International Congress of Mathematicians. [2]
• Oded Goldreich. Combinatorial Property Testing (a survey). [3][4]
• Jacob Fox, A new proof of the graph removal lemma, to appear in Annals of Mathematics. [5]