SAT Certificates for the Matrix-Multiplication Challenges over F2: All Ten `Expected-UNSAT` Instances Are Satisfiable, and a Type-3-Free Rank-23 Scheme

تخيل أنك تحاول حل أحجية قطع تركيب (jigsaw puzzle) ضخمة ثلاثية الأبعاد. لكنها ليست صورة لغروب الشمس أو قطة؛ بل هي آلة رياضية مصممة لضرب شبكتين من الأرقام معاً. في عالم علوم الحاسوب والرياضيات، يُطلق على هذا اسم "ضرب المصفوفات" (matrix multiplication). لعقود من الزمن، كان الرياضيون يبحثون عن الطريقة الأكثر كفاءة لبناء هذه الآلة. إنهم يريدون معرفة الحد الأدنى المطلق لعدد وحدات البناء الأساسية الصغيرة (التي تسمى "عمليات الضرب") اللازمة لجعل هذا الشيء بأكمله يعمل.

فكر في وحدات البناء هذه كأنها قطع "ليجو" (Lego). لفترة طويلة، كان الجميع يعرف كيف يبني آلة ضرب 3×3 باستخدام 23 قطعة. والسؤال الكبير كان: هل يمكننا بناؤها بـ 22 قطعة فقط؟ وللعثور على الإجابة، حول الباحثون المشكلة إلى لغز منطقي ضخم، يشبه تلك الألغاز التي قد تراها في ألعاب الفيديو أو كتب "السودوكو"، ولكن بمقياس يجعل رأسك يدور. لقد قاموا بتشفير قواعد الرياضيات في تنسيق يمكن للحواسيب التحقق منه، وهو ما يسمى مشكلة "الرضا" (SAT) (والتي تعني القابلية للتحقق). إذا استطاع الحاسوب إيجاد طريقة لقلب جميع المفاتيح إلى وضع التشغيل "on" دون كسر أي قواعد، فقد تم حل اللغز. وإذا قال الحاسوب "مستحيل"، فربما لا تكفي 2 22 قطعة. يغوص هذا البحث في مجموعة محددة من هذه الألغاز المنطقية التي صُممت لاختبار حدود حواسيبنا الحالية وفهمنا لهذه الآلات الرياضية.

---

اللغز العظيم "المستحيل" الذي لم يكن كذلك

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

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

لقد كتب مبتكرو اللغز القواعد باستخدام تعليمات "إيجابية". قالوا: "يجب أن يكون لديك هذه القطعة المحددة هنا"، و"يجب أن تكون تلك القطعة هناك". لكنهم نسوا أن يقولوا: "ولا يجوز أن تلمس هذه القطع أي قطع أخرى". واتضح أن الرياضيات تسمح بإضافة قطع إضافية، طالما أن الآلة النهائية لا تزال تعمل بشكل صحيح. كانت الألغاز "المستحيلة" في الواقع تنتظر شخصاً يدرك أن الباب ليس مغلقاً؛ بل كان الأمر فقط أن الجميع يحاولون وضع قطع الأحجية في صندوق صغير جداً، متجاهلين حقيقة أن الصندوق يمكن أن يكون أكبر قليلاً.

سحر الإزاحة والتبديل

إذاً، كيف حل بالادينوس هذه الألغاز؟ لقد استخدم خدعة ذكية تتعلق بـ "التماثل" (symmetry). تخيل أن لديك مكعب روبيك. إذا قمت بتدوير المكعب بالكامل أو تدويره، ستتحرك الألوان، لكن المكعب يظل هو نفسه. أدرك بالادينوس أن الآلة الرياضية التي يبنيها لها خاصية مماثلة. يمكنه أخذ حل يعمل (مجموعة من 23 قطعة تنجح في ضرب المصفوفات) ثم تدويرها، أو تدويرها، أو إعادة ترتيب القطع حولها باستخدام رقصة رياضية خاصة تسمى "عمل المجموعة GL(3, 2)".

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

وتخيل ماذا حدث؟ لقد تناسبت تماماً!

في الواقع، لم يجد بالادينوس حلاً واحداً فحسب؛ بل وجد حلولاً لجميع الألغاز العشرة التي كان من المفترض أن تكون مستحيلة. لقد أثبت أن هذه الصيغ "غير القابلة للحل" هي في الواقع "قابلة للتحقق" (satisfiable). لم يقم الحاسوب بمجرد التخمين؛ بل تحقق من كل قاعدة. تؤكد الورقة البحثية أنه بالنسبة لجميع ملفات "التحدي 2" العشرة، توجد طريقة صالحة لترتيب الـ 23 قطعة لبناء الآلة لتعمل. لم يكن وصف "المستحيل" سوء فهم، بل كان سوء فهم للقواعد، وليس عائقاً رياضياً حقيقياً.

"القطعة الشبح" والحل المثالي

تناولت الورقة أيضاً تحدياً ثالثاً، وهو "التحدي 3". طرح هذا التحدي سؤالاً مختلفاً: هل يمكننا بناء الآلة باستخدام 23 قطعة، مع التأكد من أن قطعة واحدة منها "شبحية"؟ في لغة الرياضيات، يعني هذا أن إحدى الـ 23 قطعة يجب أن يكون "عدّ النوع-3" (type-3 count) الخاص بها صفراً. وهذه طريقة معقدة لقول إن إحدى القطع لا ينبغي أن تشارك في نمط معين شائع يظهر عادة في هذه الآلات.

تمكن بالادينوس من فعل ذلك أيضاً. بدأ بحل يعمل وقام بتبديل دقيق للغاية. أخذ قطعتين تقومان بوظيفة معينة واستبدلهما بقطعتين مختلفتين تقومان بنفس الوظيفة تماماً ولكن تبدوان مختلفتين. كان هذا التبديل ذكياً جداً لدرجة أنه خلق قطعة "شبحية" — قطعة لا تثير النمط المحظور على الإطلاق. لقد أثبت أنه يمكنك بالفعل بناء آلة ضرب المصفوفات 3×3 باستخدام 23 قطعة، حيث تكون إحدى هذه القطع خالية تماماً من ذلك النمط المحدد.

الفحص النهائي

للتأكد من أنه لا يمكن لأحد أن يقول: "أوه، لقد كنت محظوظاً فقط باستخدام الحاسوب"، قام بالادينوس ببناء برنامج فحص صارم للغاية. قام بإنشاء القائمة الكاملة لـ 26,541 متغيراً (المفاتيح) لجميع الألغاز الـ 21 (10 من التحدي 1، و10 من التحدي 2، و1 من التحدي 3). ثم قام بتشغيل برنامج منفصل يقرأ قواعد اللغز الأصلية والحلول الجديدة، ويتحقق من كل بند من بنود الـ 2,461,316 بنداً منطقياً.

النتيجة؟ صفر حالات فشل. كل قاعدة تم استيفاؤها. الحلول حقيقية، ومحققة، وقابلة لإعادة الإنتاج. يمكن لأي شخص لديه البرنامج المناسب تشغيل نفس الكود والحصول على نفس الإجابة في حوالي تسع ثوانٍ.

ماذا يعني هذا (وماذا لا يعني)

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

ومع ذلك، هناك ملاحظة. تحل هذه الورقة الألغاز لنوع محدد من عالم الرياضيات يسمى "F2" (وهو يشبه عالماً حيث الأرقام تلتف فقط بعد الرقم 1، أي أن 1+1=0). هي لا تثبت أننا نستطيع بناء آلة بـ 22 قطعة. إن البحث عن آلة الـ 22 قطعة (التحدي 4) لا يزال مفتوحاً. كما أن الورقة لا تقول إن هذه الحلول تعمل في كل نوع من أنواع الرياضيات التي قد تستخدمها في العالم الحقيقي، مثل الأعداد المركبة المستخدمة في الهندسة. إنها فقط تحل الألغاز المنطقية كما كُتبت.

لكن بالنسبة للألغاز التي كُتبت، فإن الحكم واضح: "المستحيل" هو في الواقع "ممكن". الباب لم يكن مغلقاً أبداً؛ كنا نحتاج فقط إلى المفتاح الصحيح لتدوير المقبض.