اختبار الخصائص

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
الموسوعة الحرة

اختبار الخصائص هو مجال من مجالات علوم الحاسوب النظرية ، يهتم بتصميم خوارزميات فائقة السرعة لاتخاذ القرارات التقريبية، حيث يشير القرار إلى خصائص أو معايير الأجسام الضخمة. [ 1 ]

خوارزمية اختبار الخصائص لمسألة اتخاذ القرار هي خوارزمية يكون تعقيد استعلامها (عدد الاستعلامات المُرسلة إلى مُدخلاتها) أصغر بكثير من حجم المسألة. تُستخدم خوارزميات اختبار الخصائص عادةً لتحديد ما إذا كان هيكل توافقي S (مثل رسم بياني أو دالة منطقية ) يُحقق خاصية P ، أو أنه "بعيد" عن تحقيق هذه الخاصية (بمعنى أنه يجب تعديل جزء ε من تمثيل S لجعله يُحقق P ) ، وذلك باستخدام عدد قليل فقط من الاستعلامات "المحلية" للكائن. [ 2 ] [ 3 ]

على سبيل المثال، تقبل مسألة الوعد التالية خوارزمية يكون تعقيد الاستعلام فيها مستقلاً عن حجم المثال (لثابت اختياري ε > 0 ):

"بالنظر إلى رسم بياني على n رأس، قرر ما إذا كان ثنائي الأجزاء ، أو لا يمكن جعله ثنائي الأجزاء حتى بعد إزالة مجموعة فرعية عشوائية من ε n 2 حافة على الأكثر."

تعتبر خوارزميات اختبار الخصائص أساسية لتعريف البراهين القابلة للتحقق احتماليًا ، حيث أن البرهان القابل للتحقق احتماليًا هو في الأساس برهان يمكن التحقق منه بواسطة خوارزمية اختبار الخصائص.

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

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

  • إذا كان x موجودًا في L ، فإن الخوارزمية تقبل x باحتمالية لا تقل عن 2/3.
  • إذا كان x بعيدًا بمقدار ε عن L ، فإن الخوارزمية ترفض x باحتمالية لا تقل عن 2/3.

هنا، تعني عبارة " x بعيد عن L بمقدار ε " أن مسافة هامينغ بين x وأي سلسلة في L هي على الأقل ε | x | .

يقال إن خوارزمية اختبار الخصائص تحتوي على خطأ من جانب واحد إذا كانت تفي بالشرط الأقوى وهو أن احتمال القبول للحالات x ∈ L هو 1 بدلاً من 2/3.

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

الميزات والقيود

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

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

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

اختبار خصائص الرسم البياني

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

لتوضيح المفاهيم العامة لاختبار الخصائص في سياق الرسوم البيانية، نقول إن مُختبِر خاصية الرسم البياني P يجب أن يُميّز، باحتمالية لا تقل عن ثلثي الاحتمالية، بين حالتي تحقق الرسم البياني G للخاصية P وحالة كون G على بُعد ε من حيث مسافة التحرير من حالة تحقق P. يمكن للمُختبِر الوصول إلى وسيط للاستعلام عما إذا كان هناك ضلع يربط بين رأسين في G أم لا. تعقيد الاستعلام هو عدد استعلامات الوسيط هذه. يُقال إن المُختبِر لديه خطأ من جانب واحد إذا كانت لديه نتائج إيجابية خاطئة وليس نتائج سلبية خاطئة، أي إذا كان G يحقق الخاصية P ، فإن المُختبِر يُخرج دائمًا الإجابة الصحيحة. [ 4 ] [ 5 ]

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

نبذة تاريخية

طُرح مجال اختبار خصائص الرسوم البيانية لأول مرة على يد غولدريتش، وغولدواسير، ورون. في ورقتهم البحثية الرائدة المنشورة عام ١٩٩٨، تم تحليل مشكلة تقسيم الرسوم البيانية المجردة، وقُدِّمت بعض أدوات الاختبار. تشمل هذه الأدوات، كحالات خاصة، العديد من خصائص الرسوم البيانية المهمة مثل ثنائية الأجزاء ، وإمكانية التلوين بـ k لون ، ووجود زمرة كبيرة ، ووجود قطع كبير . [ ٤ ] على وجه الخصوص، فإن الخوارزميات الطبيعية التي تأخذ عينة من رسم بياني فرعي وتتحقق مما إذا كان يحقق الخاصية صحيحة جميعها، وإن كانت ذات تعقيد استعلام قد لا يكون مثاليًا.

ومنذ ذلك الحين، تم التوصل إلى العديد من الاكتشافات ذات الصلة.

  • في عام 1992، أظهر كل من ألون، ودوك، وليفمان، ورودل، ويستر أنه بالنسبة لكل رسم بياني H ، فإن خاصية عدم احتواء H كرسم بياني فرعي قابلة للاختبار. [ 6 ]
  • في عام 1999، أظهر كل من ألون وفيشر وكريفليفيتش وسيجيدي أنه بالنسبة لكل رسم بياني H ، فإن خاصية عدم احتواء H كرسم بياني فرعي مستحث قابلة للاختبار. [ 7 ]
  • في عام 2005، أظهر ألون وشابيرا أن أي خاصية من خصائص الرسم البياني الرتيب (التي يتم الحفاظ عليها عند حذف الرؤوس والحواف) قابلة للاختبار بخطأ من جانب واحد. [ 8 ]
  • في عام 2008، عرض ألون وشابيرا نماذج اختبار ذات خطأ أحادي الجانب لجميع خصائص الرسم البياني الوراثي . كما وصفا خصائص يسهل اختبارها، وهي خصائص طبيعية شبه وراثية . سيتم توضيح هذه النقاط لاحقًا. [ 2 ]

اختبار خصائص الرسم البياني الوراثي

تُعتبر خاصية الرسم البياني وراثية إذا بقيت محفوظة عند حذف رؤوسه، أو بصورة مكافئة، إذا بقيت محفوظة عند إنشاء رسوم بيانية فرعية مستحثة . من أهم الخصائص الوراثية: خلو الرسم البياني H من الرؤوس (لبعض الرسوم البيانية H )، وقابلية تلوينه بـ k لون ، واستوائه . جميع الخصائص الوراثية قابلة للاختبار.

نظرية (ألون وشابيرا 2008). كل خاصية من خصائص الرسم البياني الوراثي قابلة للاختبار بخطأ من جانب واحد. [ 2 ]

يعتمد البرهان على صيغة من مبرهنة إزالة الرسم البياني لعائلات لانهائية من الرسوم البيانية الفرعية المستحثة. ويُعدّ تعقيد الاستعلام باستخدام هذا النهج الانتظامي كبيرًا نظرًا لحدود دالة البرج في مبرهنة سيميريدي للانتظام .

نظرية (مُبرهنة إزالة الرسم البياني اللانهائي). لكل مجموعة (قد تكون لانهائية) من الرسوم البيانية H و ε > 0 ، يوجد h 0 و δ > 0 بحيث إذا كان G رسمًا بيانيًا ذو n رأسًا مع أقل من δ n v ( H ) نسخة من H لكل H ∈ H يحتوي على h 0 رأسًا على الأكثر ، فإنه يمكن جعل G خاليًا من H عن طريق إضافة/إزالة أقل من ε n 2 حافة. ​​[ 9 ]

مختبرون غافلون

بصورة غير رسمية، يكون المختبِر غير المُدرك غير مُدرك لحجم المُدخلات. بالنسبة لخاصية الرسم البياني P ، فهو خوارزمية تأخذ كمُدخلات مُعامل ε والرسم البياني G ، ثم تعمل كخوارزمية اختبار خاصية على G للخاصية P مع مُعامل التقارب ε الذي يُجري بالضبط q ( ε ) استعلامًا على G.

التعريف: المُختبِر غير المُدرك هو خوارزمية تأخذ مُعاملًا ε كمدخل . تحسب هذه الخوارزمية عددًا صحيحًا q ( ε ) ، ثم تطلب من مُستدلٍّ رسمًا بيانيًا فرعيًا مُستحثًا H يتكون من q ( ε ) رأسًا من G، يتم اختيارها عشوائيًا وبشكل مُنتظم. بعد ذلك، تقبل الخوارزمية الرسم البياني الفرعي المُستحث H أو ترفضه (ربما عشوائيًا) وفقًا لـ ε و H. نقول إنها تختبر الخاصية P إذا قبلت G باحتمالية لا تقل عن 2/3 إذا كانت تمتلك الخاصية P ، ورفضت G باحتمالية لا تقل عن 2/3 إذا كانت G بعيدة بمقدار ε عن امتلاك الخاصية P. [ 2 ] [ 1 ] [ 10 ]

الأهم من ذلك، أن عدد الاستعلامات التي يجريها المختبِر غير المُدرك هو ثابت يعتمد فقط على ε وليس على حجم الرسم البياني المُدخل G. وبالمثل تمامًا لخوارزميات اختبار الخصائص، يمكننا الحديث عن المختبِرين غير المُدركين ذوي الخطأ أحادي الجانب.

اختبار خصائص الرسم البياني شبه الوراثي

يمكننا ابتكار بعض خصائص الرسم البياني التي يجب على المختبر الوصول إلى عدد رؤوسها.

مثال. يحقق الرسم البياني G الخاصية P إذا كان ثنائي الأجزاء بعدد زوجي من الرؤوس أو كاملًا بعدد فردي من الرؤوس. [ 2 ]

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

التعريف. تُعتبر خاصية الرسم البياني H شبه وراثية إذا وُجدت خاصية رسم بياني وراثية H بحيث أن أي رسم بياني يحقق P يحقق H ، ولكل ε > 0 ، يوجد M ( ε ) بحيث أن كل رسم بياني بحجم M ( ε ) على الأقل والذي يبعد ε- عن تحقيق P يحتوي على رسم بياني فرعي مستحث لا يحقق H. [ 2 ]

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

نظرية (ألون وشابيرا 2008). خاصية الرسم البياني P لها مُختبِر خطأ أحادي الجانب غير واعٍ إذا وفقط إذا كانت P شبه وراثية. [ 2 ]

أمثلة: اختبار بعض خصائص الرسم البياني

في هذا القسم، سنقدم بعض خوارزميات الاختبار الطبيعية غير الواعية ذات الخطأ أحادي الجانب لخصائص خلو الرسم البياني من المثلثات ، وثنائية الأجزاء ، وقابلية التلوين بـ k لون . وهي طبيعية لأنها تتبع الفكرة الشائعة المتمثلة في اختيار عينة عشوائية من مجموعة فرعية X من رؤوس الرسم البياني G، والتحقق من تحقق خاصية الرسم البياني على الرسم البياني الفرعي الممتد بواسطة X باستخدام البحث الشامل . لدينا خطأ أحادي الجانب لأن هذه الخصائص وراثية: إذا حقق الرسم البياني G الخاصية، فيجب أن يحققها الرسم البياني الفرعي الممتد بواسطة X أيضًا ، وبالتالي فإن خوارزمية الاختبار لدينا تقبل دائمًا.

للتأكد من خلو الرسم البياني من المثلثات ، فإن أداة الاختبار هي تطبيق لفرضية إزالة المثلثات . على وجه الخصوص، تخبرنا هذه الأداة أنه إذا كان الرسم البياني G بعيدًا بمقدار ε عن كونه خاليًا من المثلثات، فإنه يوجد ثابت (قابل للحساب) δ = δ ( ε ) بحيث يحتوي G على δn³ مثلثًا على الأقل .

مثال (خوارزمية اختبار خلو المثلثات).

  1. بالنظر إلى الرسم البياني G ، اختر مجموعة عشوائية X من q ( ε ) = 1/ δ ثلاثيات من الرؤوس بشكل مستقل عشوائيًا، حيث δ كما هو مذكور أعلاه.
  2. لكل ثلاثية من الرؤوس في X ، استعلم عما إذا كانت جميع أزواج الرؤوس الثلاثة متجاورة في G.
  3. تقبل الخوارزمية إذا لم ينتج عن أي ثلاثية من الرؤوس مثلث، وترفض خلاف ذلك. [ 1 ]

لضمان ثنائية الأجزاء وقابلية التلوين بـ k لون ، لنفترض أن δ هو الحد الأعلى المطلوب لاحتمالية الخطأ للمختبِرين التاليين. تجدر الإشارة إلى أنه لا ينبغي الخلط بين تعقيد الاستعلام ووقت التشغيل. غالبًا ما يكون وقت التشغيل أُسّيًا (كما هو الحال مع كليهما) نظرًا لعدم وجود خوارزمية قرار ذات وقت متعدد الحدود لاختبار الخاصية على الرسم البياني الفرعي المُستحث. بدلًا من ذلك، نتحقق باستخدام البحث الشامل . [ 4 ]

مثال (خوارزمية اختبار ثنائية الأجزاء).

  1. بالنظر إلى الرسم البياني G ، اختر مجموعة عشوائية X من q ( ε ) = O (log(1/( ε δ ))/ ε 2 ) رؤوس.
  2. لكل زوج من الرؤوس في X ، استعلم عما إذا كانت متجاورة في G.
  3. يقبل إذا كان الرسم البياني الفرعي المستحث من G على X ثنائي الأجزاء ويرفض خلاف ذلك. [ 4 ]

مثال (خوارزمية اختبار قابلية التلوين k).

  1. بالنظر إلى الرسم البياني G ، اختر مجموعة عشوائية X من q ( ε ) = O ( k 4 log 2 ( k / δ )/ ε 3 ) رؤوس.
  2. لكل زوج من الرؤوس في X ، استعلم عما إذا كانت متجاورة في G.
  3. يقبل إذا كان الرسم البياني الفرعي المستحث من G على X قابلاً للتلوين بـ k لونًا ويرفض خلاف ذلك. [ 4 ]

مراجع

  1. 1 2 3 غولدريتش، أوديد (2017). مقدمة في اختبار الخصائص . مطبعة جامعة كامبريدج. ISBN 9781107194052.
  2. 1 2 3 4 5 6 7 8 ألون، نوغا ؛ شابيرا، آساف (2008). "توصيف خصائص الرسم البياني (الطبيعي) القابلة للاختبار بخطأ من جانب واحد" (ملف PDF) . مجلة SIAM للحوسبة . 37 (6): 1703-1727 . doi : 10.1137/06064888X .
  3. ↑ غولدريتش، أوديد (1999). "اختبار الخصائص التوافقية (دراسة استقصائية)". أساليب العشوائية في تصميم الخوارزميات . سلسلة DIMACS في الرياضيات المتقطعة وعلوم الحاسوب النظرية. المجلد 43. الصفحات 45-59 . doi : 10.1090/dimacs/043/04 . ISBN   0821870874.
  4. 1 2 3 4 5 غولدريتش، عوديد؛ غولدواسير، شافي؛ رون، دانا (1 يوليو 1998). "اختبار الخصائص وعلاقته بالتعلم والتقريب" . مجلة ACM . 45 (4): 653-750 . doi : 10.1145/285055.285060 .
  5. ↑ روبينفيلد، رونيت؛ شابيرا، آساف (2011). "خوارزميات زمن شبه خطي". مجلة SIAM للرياضيات المتقطعة . 25 (4): 1562-1588 . CiteSeerX 10.1.1.221.1797 . doi : 10.1137/100791075 . S2CID 1319122 .  
  6. ↑ ألون، ن.؛ ديوك، ر.أ.؛ ليفمان، هـ.؛ رودل، ف.؛ يوستر، ر. (1 يناير 1994). "الجوانب الخوارزمية لمعضلة الانتظام". مجلة الخوارزميات . 16 (1): 80-109 . doi : 10.1006/jagm.1994.1005 .
  7. ↑ ألون، نوجا؛ فيشر، الدار؛ كريفيليفيتش, مايكل ; سيجيدي ماريو (1 أبريل 2000). “الاختبار الفعال للرسوم البيانية الكبيرة”. كومبيناتوريكا . 20 (4): 451-476 . دوى : 10.1007 / s004930070001 .
  8. ↑ ألون، نوغا؛ شابيرا، آصف (22 مايو 2005). "كل خاصية من خصائص الرسم البياني الرتيب قابلة للاختبار". وقائع الندوة السنوية السابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 128-137 . doi : 10.1145/1060590.1060611 . ISBN  1581139608. S2CID 14096855 . 
  9. ↑ فوكس، جاكوب (2010). "برهان جديد لفرضية إزالة الرسم البياني". arXiv : 1006.1300 [ math.CO ].
  10. ↑ رون، دانا (2000). اختبار الخصائص (تقرير فني).