خوارزمية التصديق

في علم الحاسوب النظري ، تُعرَّف خوارزمية التحقق بأنها خوارزمية تُخرج، إلى جانب حل للمشكلة التي تحلها، برهانًا على صحة هذا الحل. ويُقال إن خوارزمية التحقق فعالة إذا كان زمن تشغيلها مع مدقق البرهان أبطأ بمعامل ثابت على الأكثر من أفضل خوارزمية غير معتمدة معروفة لنفس المشكلة. ^{[ 1 ]}

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

قد تُعتبر تطبيقات خوارزميات التصديق التي تتضمن أيضًا مدققًا للإثبات الناتج عن الخوارزمية أكثر موثوقية من الخوارزميات غير المعتمدة. ففي كل مرة تُشغَّل فيها الخوارزمية، يحدث أحد ثلاثة أمور: إما أن تُنتج مخرجات صحيحة (الحالة المرغوبة)، أو أن تكتشف خطأً في الخوارزمية أو في أحد دلالاتها (حالة غير مرغوبة، ولكنها أفضل عمومًا من الاستمرار دون اكتشاف الخطأ)، أو أن تكون كل من الخوارزمية والمدقق معيبة بطريقة تُخفي الخطأ وتمنع اكتشافه (حالة غير مرغوبة، ولكنها مستبعدة لأنها تعتمد على وجود خطأين مستقلين). ^{[ 1 ]}

تأتي العديد من الأمثلة على المشكلات المتعلقة بالخوارزميات القابلة للتحقق من نظرية الرسوم البيانية . على سبيل المثال، تُخرج الخوارزمية التقليدية لاختبار ما إذا كان الرسم البياني ثنائي الأجزاء قيمة منطقية: صحيح إذا كان الرسم البياني ثنائي الأجزاء، وخطأ خلاف ذلك. في المقابل، قد تُخرج خوارزمية التحقق تلوينًا ثنائيًا للرسم البياني في حالة كونه ثنائي الأجزاء، أو دورة ذات طول فردي إذا لم يكن كذلك. يكون أي رسم بياني ثنائي الأجزاء إذا وفقط إذا كان من الممكن تلوينه بلونين، وغير ثنائي الأجزاء إذا وفقط إذا كان يحتوي على دورة ذات طول فردي. قد يكون كل من التحقق من صحة التلوين الثنائي والتحقق مما إذا كان تسلسل معين من الرؤوس ذي طول فردي دورةً أبسط من اختبار ثنائية الأجزاء. ^{[ 1 ]}

وبالمثل، يمكن اختبار ما إذا كان الرسم البياني الموجه المعطى غير دوري باستخدام خوارزمية تحقق تُخرج إما ترتيبًا طوبولوجيًا أو دورة موجهة. كما يمكن اختبار ما إذا كان الرسم البياني غير الموجه وتريًا باستخدام خوارزمية تحقق تُخرج إما ترتيبًا إقصائيًا (ترتيبًا لجميع الرؤوس بحيث تُشكل الرؤوس المجاورة لكل رأس، والتي تقع لاحقًا في الترتيب، زمرة ) أو دورة غير وترية. ويمكن أيضًا اختبار ما إذا كان الرسم البياني مستويًا باستخدام خوارزمية تحقق تُخرج إما تمثيلًا مستويًا أو رسمًا بيانيًا فرعيًا لكوراتوفسكي . ^{[ 1 ]}

تُثبت خوارزمية إقليدس الموسعة لإيجاد القاسم المشترك الأكبر لعددين صحيحين x و y صحة المعادلة التالية: فهي تُخرج ثلاثة أعداد صحيحة g ( القاسم ) ، و a ، و b ، بحيث يكون ax + by = g . لا تصح هذه المعادلة إلا لمضاعفات القاسم المشترك الأكبر، لذا يمكن اختبار أن g هو القاسم المشترك الأكبر بالتحقق من أن g يقسم كلاً من x و y وأن هذه المعادلة صحيحة. ^{[ 1 ]}

• التحقق من صحة النتائج ، هو اختبار بسيط للتأكد من صحة المخرجات أو النتائج الوسيطة، ولا يُشترط أن يكون دليلاً كاملاً على الصحة.