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