براهين وجود الخوارزميات غير البنّاءة

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

بدأ مايكل فيلوز ومايكل لانغستون بدراسة البراهين الخوارزمية غير البنائية للمسائل في نظرية الرسم البياني في عام 1988. ^{[ 1 ]}

من الأسئلة الشائعة في نظرية الرسوم البيانية ما إذا كان رسم بياني معين يمتلك خاصية معينة. على سبيل المثال:

المدخلات : رسم بياني G.

السؤال: هل يمكن تضمين G في فضاء ثلاثي الأبعاد، بحيث لا تكون أي دورتين منفصلتين من G مرتبطتين طوبولوجيًا (كما هو الحال في حلقات السلسلة)؟

توجد خوارزمية ذات تعقيد أسي كبير لتحديد ما إذا كانت دورتان مضمنتان في فضاء ثلاثي الأبعاد مرتبطتان، ويمكن اختبار جميع أزواج الدورات في الرسم البياني، ولكن ليس من الواضح كيفية مراعاة جميع التضمينات الممكنة في فضاء ثلاثي الأبعاد. لذا، فليس من الواضح مسبقًا ما إذا كانت مشكلة الارتباط قابلة للحل.

مع ذلك، يوجد برهان غير بنائي يُظهر أن مسألة الترابط قابلة للتقرير في وقت متعدد الحدود. ويعتمد هذا البرهان على الحقائق التالية:

• مجموعة الرسوم البيانية التي تكون إجابتها "نعم" مغلقة تحت عملية أخذ المحددات الصغرى . أي، إذا كان من الممكن تضمين رسم بياني G بدون روابط في فضاء ثلاثي الأبعاد، فإنه يمكن أيضًا تضمين كل محدد صغرى من G بدون روابط.
• لكل رسمين بيانيين G و H ، من الممكن إيجاد في وقت متعدد الحدود ما إذا كان H هو رسم بياني صغير لـ G.
• بحسب نظرية روبرتسون-سيمور ، فإن أي مجموعة من الرسوم البيانية المحدودة لا تحتوي إلا على عدد محدود من العناصر الصغرى الدنيا. وعلى وجه الخصوص، فإن مجموعة حالات "نعم" تحتوي على عدد محدود من العناصر الصغرى الدنيا.

بفرض وجود رسم بياني G كمدخل ، فإن "الخوارزمية" التالية تحل المشكلة المذكورة أعلاه:

لكل عنصر أصغر-أصغر H :

إذا كان H مصغرًا لـ G ، فأرجع "نعم".

إرجاع "لا".

الجزء غير البنّاء هنا هو نظرية روبرتسون-سيمور. فرغم أنها تضمن وجود عدد محدود من العناصر الصغرى الدنيا، إلا أنها لا تُحدد ماهية هذه العناصر. لذا، لا يُمكننا فعلياً تنفيذ "الخوارزمية" المذكورة أعلاه. لكننا نعلم بوجود خوارزمية وأن زمن تشغيلها متعدد الحدود.

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

الفكرة الأساسية هي أنه يمكن حل مشكلة ما باستخدام خوارزمية تستخدم، كمعامل، مجموعة غير معروفة. على الرغم من أن المجموعة غير معروفة، إلا أننا نعلم أنها يجب أن تكون محدودة، وبالتالي توجد خوارزمية ذات زمن متعدد الحدود.

هناك العديد من المسائل التوافقية الأخرى التي يمكن حلها باستخدام تقنية مماثلة. ^{[ 2 ]}