एक कंप्यूटर-सहायता प्राप्त प्रमाण ‘पैकिंग रंग’ समस्या का समाधान करता है -TGN

हालाँकि, ह्यूल ने पिछले परिणामों की खोज को स्फूर्तिदायक पाया। इसने प्रदर्शित किया कि अन्य शोधकर्ताओं ने समस्या को काम करने के लिए काफी महत्वपूर्ण पाया, और उनके लिए पुष्टि की कि प्राप्त करने योग्य एकमात्र परिणाम समस्या को पूरी तरह से हल करना था।

उन्होंने कहा, “एक बार जब हमें पता चला कि समस्या पर 20 साल का काम हुआ है, तो तस्वीर पूरी तरह से बदल गई।”

अश्लीलता से बचना

इन वर्षों में, ह्यूले ने विशाल संभावित संयोजनों के बीच खोज करने के कुशल तरीके खोजने में अपना करियर बनाया था। उनके दृष्टिकोण को SAT सॉल्विंग कहा जाता है – जिसका संक्षिप्त रूप “संतोषजनकता” है। इसमें एक लंबे सूत्र का निर्माण शामिल है, जिसे बूलियन सूत्र कहा जाता है, जिसके दो संभावित परिणाम हो सकते हैं: 0 या 1. यदि परिणाम 1 है, तो सूत्र सत्य है, और समस्या संतुष्ट है।

पैकिंग रंग समस्या के लिए, सूत्र में प्रत्येक चर यह दर्शा सकता है कि किसी दिए गए सेल पर किसी दिए गए नंबर का कब्जा है या नहीं। एक कंप्यूटर सूत्र को संतुष्ट करने के लिए चर निर्दिष्ट करने के तरीकों की तलाश करता है। यदि कंप्यूटर ऐसा कर सकता है, तो आप जानते हैं कि आपके द्वारा निर्धारित शर्तों के तहत ग्रिड को पैक करना संभव है।

दुर्भाग्यवश, बूलियन फॉर्मूला के रूप में पैकिंग रंग समस्या का एक सीधा एन्कोडिंग कई लाखों शब्दों तक फैल सकता है – एक कंप्यूटर, या यहां तक ​​​​कि कंप्यूटर का एक बेड़ा, इसके भीतर चर निर्दिष्ट करने के सभी अलग-अलग तरीकों का परीक्षण हमेशा के लिए चला सकता है।

गोडार्ड ने कहा, “यदि आपने इसे भोलेपन से किया तो इस क्रूर प्रयास को करने में ब्रह्मांड समाप्त होने तक का समय लगेगा।” “तो आपको इसे कुछ हद तक संभव बनाने के लिए कुछ अच्छे सरलीकरणों की आवश्यकता है।”

इसके अलावा, हर बार जब आप पैकिंग रंग की समस्या में कोई संख्या जोड़ते हैं, तो संभावित संयोजनों के बढ़ने के कारण यह लगभग 100 गुना कठिन हो जाता है। इसका मतलब यह है कि यदि समानांतर में काम करने वाले कंप्यूटरों का एक बैंक गणना के एक ही दिन में 12 को खारिज कर सकता है, तो उन्हें 13 को खारिज करने के लिए 100 दिनों के गणना समय की आवश्यकता होगी।

ह्यूले और सुबरकेसो ने एक तरह से क्रूर-बल कम्प्यूटेशनल दृष्टिकोण को अश्लील माना। “हमारे पास कई आशाजनक विचार थे, इसलिए हमने ‘आइए अपने दृष्टिकोण को अनुकूलित करने का प्रयास करें’ की मानसिकता अपनाई जब तक कि हम क्लस्टर पर 48 घंटे से कम की गणना में इस समस्या को हल नहीं कर लेते,” सुबरकेसो ने कहा।

ऐसा करने के लिए, उन्हें कंप्यूटिंग क्लस्टर द्वारा आज़माए जाने वाले संयोजनों की संख्या को सीमित करने के तरीकों के साथ आना पड़ा।

“(वे) इसे न केवल हल करना चाहते हैं, बल्कि इसे प्रभावशाली तरीके से हल करना चाहते हैं,” कहा अलेक्जेंडर सोइफ़र कोलोराडो विश्वविद्यालय, कोलोराडो स्प्रिंग्स के।

ह्यूले और सुबेरकेसो ने माना कि कई संयोजन मूलतः एक जैसे ही होते हैं। यदि आप हीरे के आकार की टाइल को आठ अलग-अलग संख्याओं से भरने का प्रयास कर रहे हैं, तो इससे कोई फर्क नहीं पड़ता कि आप जो पहला नंबर डालते हैं वह एक ऊपर और एक केंद्र वर्ग के दाईं ओर, या एक नीचे और एक बाईं ओर होता है। मध्य वर्ग. दोनों प्लेसमेंट एक-दूसरे के साथ सममित हैं और आपके अगले कदम को बिल्कुल उसी तरह से रोकते हैं, इसलिए उन दोनों की जांच करने का कोई कारण नहीं है।

यदि प्रत्येक पैकिंग समस्या को शतरंज की बिसात पैटर्न के साथ हल किया जा सकता है, जहां 1s का एक विकर्ण ग्रिड पूरे स्थान को कवर करता है (जैसे शतरंज की बिसात पर अंधेरे स्थान), तो गणना को काफी सरल बनाया जा सकता है। फिर भी यह हमेशा मामला नहीं होता है, जैसा कि 14 संख्याओं से भरी एक सीमित टाइल के इस उदाहरण में है। शतरंज की बिसात का पैटर्न ऊपर बाईं ओर कुछ स्थानों पर टूटा होना चाहिए।बर्नार्डो सुबेरकेसो और मारिज़न ह्यूले के सौजन्य से

(टैग्सटूट्रांसलेट)क्वांटा पत्रिका(टी)गणित(टी)गणित(टी)पहेलियाँ(टी)कॉम्बिनेटरिक्स(टी)कंप्यूटर