ومع ذلك ، وجد هيول أن اكتشاف النتائج السابقة أمر نشط. لقد أظهر أن باحثين آخرين وجدوا المشكلة مهمة بما يكفي للعمل عليها ، وأكدوا له أن النتيجة الوحيدة التي تستحق الحصول عليها هي حل المشكلة تمامًا.
قال: “بمجرد أن اكتشفنا أنه كان هناك 20 عامًا من العمل على المشكلة ، أدى ذلك إلى تغيير الصورة تمامًا”.
تجنب المبتذلة
على مر السنين ، اكتسب Heule مهنة من إيجاد طرق فعالة للبحث بين مجموعات واسعة ممكنة. يُطلق على نهجه اسم حل SAT – اختصارًا لـ “الرضا”. يتضمن إنشاء صيغة طويلة ، تسمى الصيغة المنطقية ، والتي يمكن أن يكون لها نتيجتان محتملتان: 0 أو 1. إذا كانت النتيجة 1 ، فإن الصيغة صحيحة ، وتم استيفاء المشكلة.
بالنسبة لمشكلة تلوين التعبئة ، قد يمثل كل متغير في الصيغة ما إذا كانت خلية معينة مشغولة برقم معين. يبحث الكمبيوتر عن طرق لتعيين المتغيرات من أجل تلبية الصيغة. إذا كان الكمبيوتر قادرًا على القيام بذلك ، فأنت تعلم أنه من الممكن حزم الشبكة وفقًا للشروط التي حددتها.
لسوء الحظ ، يمكن أن يمتد الترميز المباشر لمشكلة تلوين التعبئة كصيغة منطقية إلى ملايين المصطلحات – يمكن لجهاز الكمبيوتر ، أو حتى أسطول من أجهزة الكمبيوتر ، أن يعمل إلى الأبد لاختبار جميع الطرق المختلفة لتعيين المتغيرات داخله.
قال جودارد: “إن محاولة القيام بهذه القوة الغاشمة ستستغرق حتى ينتهي الكون إذا فعلت ذلك بسذاجة”. لذا فأنت بحاجة إلى بعض التبسيط الرائع لتخفيضه إلى شيء ممكن.
علاوة على ذلك ، في كل مرة تضيف فيها رقمًا إلى مشكلة تلوين التعبئة ، يصبح الأمر أكثر صعوبة بنحو 100 مرة ، نظرًا لطريقة تكاثر المجموعات الممكنة. هذا يعني أنه إذا كان بإمكان بنك من أجهزة الكمبيوتر التي تعمل بالتوازي استبعاد 12 في يوم واحد من الحساب ، فسيحتاجون إلى 100 يوم من وقت الحساب لاستبعاد 13.
اعتبر هيول وسوبركاسو توسيع نطاق نهج حساب القوة الغاشمة مبتذلاً بطريقة ما. قال سوبركاسو: “كان لدينا العديد من الأفكار الواعدة ، لذلك اتخذنا عقلية” دعونا نحاول تحسين نهجنا حتى نتمكن من حل هذه المشكلة في أقل من 48 ساعة من الحساب على الكتلة “.
للقيام بذلك ، كان عليهم أن يبتكروا طرقًا للحد من عدد التركيبات التي يتعين على مجموعة الحوسبة تجربتها.
“[They] قال ألكسندر سويفر من جامعة كولورادو ، كولورادو سبرينغز ، “لا نريد حلها فحسب ، بل نريد حلها بطريقة مثيرة للإعجاب”.
أدرك هيول والكازو الفرعيون أن العديد من المجموعات هي نفسها في الأساس. إذا كنت تحاول ملء بلاطة على شكل ماسة بثمانية أرقام مختلفة ، فلا يهم إذا كان الرقم الأول الذي تضعه واحدًا لأعلى والآخر على يمين المربع المركزي ، أو واحدًا لأسفل وواحدًا على يسار ساحة المركز. الموضعان متماثلان مع بعضهما البعض ويقيدان حركتك التالية بنفس الطريقة ، لذلك ليس هناك سبب للتحقق من كليهما.
إذا كان من الممكن حل كل مشكلة تعبئة بنمط رقعة الشطرنج ، حيث تغطي شبكة قطرية من 1 ثانية المساحة بأكملها (مثل المساحات المظلمة على رقعة الشطرنج) ، يمكن تبسيط الحسابات إلى حد كبير. ومع ذلك ، هذا ليس هو الحال دائمًا ، كما في هذا المثال للبلاط المحدود المليء بـ 14 رقمًا. يجب كسر نمط رقعة الشطرنج في أماكن قليلة باتجاه أعلى اليسار.بإذن من برناردو سوبركاسو ومارين هيول
