💻 computer science

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

यह शोध पत्र यह प्रदर्शित करता है कि $\mathbb{F}_2$ पर सभी दस पूर्ववर्ती "अपेक्षित-असंतोषजनक" (expected-unsatisfiable) रैंक-23 मैट्रिक्स-गुणन सूत्र वास्तव में संतत (satisfiable) हैं और इन उदाहरणों के लिए पूर्ण प्रमाण (complete certificates) के साथ एक नया रैंक-23 स्कीम प्रदान करता है जिसमें एक टाइप-3-मुक्त (type-3-free) समंक (summand) शामिल है।

मूल लेखक: Nick Palladinos

प्रकाशित 2026-08-03

📖 8 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Nick Palladinos

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल, तीन-आयामी (three-dimensional) जिग्सॉ पहेली को हल करने की कोशिश कर रहे हैं। लेकिन यह किसी सूर्यास्त या बिल्ली की तस्वीर नहीं है; यह संख्याओं के दो ग्रिडों को आपस में गुणा करने वाली एक गणितीय मशीन है। कंप्यूटर विज्ञान और गणित की दुनिया में, इसे "मैट्रिक्स मल्टीप्लिकेशन" (matrix multiplication) कहा जाता है। दशकों से, गणितज्ञ इस मशीन को बनाने का सबसे कुशल तरीका खोजने की तलाश में हैं। वे जानना चाहते हैं कि इस पूरे काम को करने के लिए न्यूनतम संख्या में छोटे, बुनियादी निर्माण खंडों (जिन्हें "गुणा" या multiplications कहा जाता है) की आवश्यकता होगी।

इन निर्माण खंडों को लेगो ब्रिक्स (Lego bricks) की तरह समझें। लंबे समय तक, सभी को पता था कि 3x3 गुणा करने वाली मशीन को 23 ब्रिक्स का उपयोग करके बनाया जा सकता है। बड़ा सवाल यह था: क्या हम इसे केवल 22 ब्रिक्स के साथ बना सकते हैं? इस समस्या को हल करने के लिए, शोधकर्ताओं ने इसे एक विशाल तर्क पहेली (logic puzzle) में बदल दिया, जो वीडियो गेम या सुडोकू की पहेलियों के समान है, लेकिन एक ऐसे पैमाने पर जो आपके सिर को घुमा दे। उन्होंने गणित के नियमों को एक ऐसे प्रारूप में एनकोड किया जिसे कंप्यूटर जांच सके, जिससे एक "SAT" समस्या (जो 'सैटिस्फिएबिलिटी' या Satisfiability को दर्शाता है) बनी। यदि कंप्यूटर सभी स्विचों को बिना किसी नियम को तोड़े "ऑन" करने का तरीका ढूंढ लेता है, तो पहेली हल हो जाती है। यदि कंप्यूटर कहता है "असंभव," तो शायद 22 ब्रिक्स पर्याप्त नहीं हैं। यह शोध पत्र इन विशिष्ट प्रकार की तर्क पहेलियों में से एक का अध्ययन करता है जिन्हें हमारे वर्तमान कंप्यूटरों और इन गणितीय मशीनों के बारे में हमारी समझ की सीमाओं का परीक्षण करने के लिए डिज़ाइन किया गया था।

वह महान "असंभव" पहेली जो वास्तव में संभव थी

निक पालाडिनोस (Nick Palladinos) से मिलिए, एक डिजिटल जासूस जिसने दस तर्क पहेलियों के एक सेट पर एक नया दृष्टिकोण देखने का निर्णय लिया, जिन्हें बाकी सबने छोड़ दिया था। ये पहेलियाँ, जिन्हें "चैलेंज 2" (Challenge 2) उदाहरण कहा जाता है, अन्य शोधकर्ताओं द्वारा एक बहुत ही विशिष्ट और कठोर नियमों के सेट के साथ बनाई गई थीं। पहेली बनाने वालों का मानना था कि वे "असंभव" थीं। उन्हें लगा कि नियम इतने सख्त थे कि 23 लेगो ब्रिक्स का कोई भी संयोजन इस मशीन को बनाने के लिए फिट नहीं हो सकता। यह ऐसा था जैसे आपसे कहा गया हो, "यहाँ एक डिब्बा है जिसमें एक ताला लगा है जिसे निश्चित रूप से खोला नहीं जा सकता," और सबने बस सिर हिलाया और चले गए।

लेकिन पालाडिनोस ने केवल एक बड़े हथौड़े से ताले को खोलने की कोशिश नहीं की। इसके बजाय, उन्होंने ताले को खुद देखा और महसूस किया कि नियम उतने सख्त नहीं थे जितना सोचा गया था।

पहेली बनाने वालों ने नियमों को "सकारात्मक" निर्देशों के साथ लिखा था। उन्होंने कहा, "आपको यहाँ यह विशिष्ट ब्रिक चाहिए," और "आपको वहाँ वह ब्रिक चाहिए।" लेकिन वे यह कहना भूल गए, "और आपके पास इन अन्य ब्रिक्स के साथ कोई अन्य ब्रिक नहीं होना चाहिए।" यह सच है कि गणित अतिरिक्त ब्रिक्स जोड़ने की अनुमति देता है, जब तक कि अंतिम मशीन सही ढंग से काम करती रहे। वे "असंभव" पहेलियाँ वास्तव में केवल किसी के यह समझने का इंतज़ार कर रही थीं कि दरवाज़ा बंद नहीं था; बस यह था कि हर कोई पहेली के टुकड़ों को एक ऐसे बॉक्स में फिट करने की कोशिश कर रहा था जो बहुत छोटा था, जबकि वे इस तथ्य को अनदेखा कर रहे थे कि बॉक्स वास्तव में थोड़ा बड़ा हो सकता था।

शिफ्टिंग और स्वैपिंग का जादू

तो, पालाडिनोस ने उन्हें कैसे हल किया? उन्होंने "सिमेट्री" (Symmetry) का उपयोग करते हुए एक चतुर ट्रिक का इस्तेमाल किया। कल्पना कीजिए कि आपके पास एक रुबिक क्यूब है। यदि आप पूरे क्यूब को घुमाते हैं या रोटेट करते हैं, तो रंग इधर-उधर हो जाते हैं, लेकिन क्यूब वही रहता है। पालाडिनोस ने महसूस किया कि वह गणितीय "मशीन" जिसे वह बना रहे थे, में एक समान गुण था। वह एक काम करने वाले समाधान (23 ब्रिक्स का एक सेट जो सफलतापूर्वक मैट्रिक्स को गुणा करता है) को ले सकते थे और टुकड़ों को "GL(3, 2) ग्रुप एक्शन" नामक एक विशेष गणितीय नृत्य का उपयोग करके घुमा, रोटेट या व्यवस्थित कर सकते थे।

इसे कमरे में फर्नीचर को फिर से व्यवस्थित करने जैसा समझें। आप सोफे को बाईं ओर, लैंप को दाईं ओर और कालीन को बीच में रख सकते हैं। कमरा अभी भी एक कमरा ही रहता है, और फर्नीचर अभी भी काम करता है, लेकिन लेआउट अलग होता है। पालाडिनोस ने एक काम करने वाले समाधान को लिया और इन गणितीय "घुमावों" (twists) को लागू किया। फिर, उन्होंने यह देखने के लिए एक मिलान खेल (matching game) का उपयोग किया कि क्या फर्नीचर के ये नए, पुनर्व्यवस्थित संस्करण उन विशिष्ट "स्लॉट्स" में फिट हो सकते हैं जो पेचीदा पलों की पहेलियों द्वारा आवश्यक थे।

और क्या आप जानते हैं? वे पूरी तरह से फिट हो गए!

वास्तव में, पालाडिनोस ने केवल एक समाधान नहीं खोजा; उन्होंने उन सभी दस पहेलियों के लिए समाधान खोजे जो असंभव मानी जा रही थीं। उन्होंने साबित किया कि ये "असंतुष्ट" (unsolvable) सूत्र वास्तव में संतुष्ट करने योग्य (satisfiable) हैं। कंप्यूटर ने केवल अनुमान नहीं लगाया; इसने हर एक नियम की जाँच की। शोध पत्र पुष्टि करता है कि इन सभी 10 "चैलेंज 2" फाइलों के लिए, 23 निर्माण खंडों को व्यवस्थित करने का एक वैध तरीका है जिससे मशीन काम करती है। "असंभव" लेबल नियमों की एक गलतफहमी थी, न कि कोई वास्तविक गणितीय बाधा।

"घोस्ट" ब्रिक और पूर्ण समाधान

शोध पत्र ने एक तीसरे चैलेंज, "चैलेंज 3" को भी संबोधित किया। यह एक अलग प्रश्न पूछ रहा था: क्या हम मशीन को 23 ब्रिक्स का उपयोग करके बना सकते हैं, लेकिन यह सुनिश्चित कर सकते हैं कि एक विशिष्ट ब्रिक "घोस्टली" (ghostly) हो? गणित की भाषा में, इसका अर्थ है कि 23 निर्माण खंडों में से एक का "टाइप-3 काउंट" शून्य होना चाहिए। यह कहने का एक फैंसी तरीका है कि एक ब्रिक को एक विशिष्ट, सामान्य पैटर्न में भाग नहीं लेना चाहिए जो आमतौर पर इन मशीनों में दिखाई देता है।

पालाडिनोस यह भी करने में सफल रहे। उन्होंने एक काम करने वाले समाधान से शुरुआत की और एक बहुत ही सटीक बदलाव (swap) किया। उन्होंने दो ब्रिक्स को लिया जो एक विशिष्ट काम कर रहे थे और उन्हें दो अलग ब्रिक्स से बदल दिया जो ठीक वही काम करते थे लेकिन दिखने में अलग थे। यह बदलाव इतना चतुर था कि इसने एक "घोस्ट" ब्रिक बना दिया—एक ऐसा ब्रिक जो उस विशिष्ट पैटर्न को बिल्कुल भी ट्रिगर नहीं करता है। उन्होंने सिद्ध किया कि आप वास्तव में 23 ब्रिक्स के साथ 3x3 मैट्रिक्स गुणन मशीन बना सकते हैं, जहाँ उनमें से एक उस विशिष्ट पैटर्न से पूरी तरह मुक्त है।

अंतिम जाँच

यह सुनिश्चित करने के लिए कि कोई यह न कह सके कि, "ओह, आपने बस कंप्यूटर के साथ किस्मत आजमा ली," पालाडिनोस ने एक अत्यंत सख्त चेकर बनाया। उन्होंने सभी 21 पहेलियों (10 चैलेंज 1 से, 10 चैलेंज 2 से, और 1 चैलेंज 3 से) के लिए पूर्ण 26,541 वेरिएबल्स (स्विचों) की सूची तैयार की। फिर उन्होंने एक अलग प्रोग्राम चलाया जिसने मूल पहेली के नियमों और नए समाधानों को पढ़ा, और प्रत्येक एक के 2,461,316 तार्किक क्लॉज़ (logical clauses) की जाँच की।

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

इसका क्या अर्थ है (और क्या नहीं)

तो, मुख्य निष्कर्ष क्या है? शोध पत्र दिखाता है कि "असंभव" पहेलियाँ वास्तव में हल करने योग्य थीं; नियम उतने सख्त नहीं थे जितना पहेली बनाने वालों ने सोचा था। यह एक याद दिलाता है कि गणित और कंप्यूटर विज्ञान में, कभी-कभी सबसे कठिन काम समाधान खोजना नहीं होता, बल्कि यह महसूस करना होता है कि समस्या उतनी टूटी हुई नहीं है जितनी वह दिखती है।

हालाँकि, एक पेच है। यह शोध पत्र "F2" नामक गणित की दुनिया के लिए पहेलियों को हल करता है (जो कि ऐसी दुनिया है जहाँ संख्याएँ केवल 1 के बाद वापस घूम जाती हैं, यानी 1+1=0)। यह यह सिद्ध नहीं करता है कि हम 22-ब्रिक्स वाली मशीन बना सकते हैं। 22-ब्रिक्स वाली मशीन की खोज (चैलेंज 4) अभी भी खुली है। यह शोध पत्र यह भी नहीं कहता कि ये समाधान हर उस तरह के गणित के लिए काम करेंगे जिसका आप वास्तविक दुनिया में उपयोग कर सकते हैं, जैसे कि इंजीनियरिंग में उपयोग किए जाने वाले जटिल अंक (complex numbers)। यह केवल लिखे गए विशिष्ट तर्क पहेलियों को हल करता है।

लेकिन जिन पहेलियों को लिखा गया था, उनके लिए फैसला स्पष्ट है: "असंभव" वास्तव में संभव है। दरवाजा कभी बंद नहीं था; हमें बस हैंडल घुमाने के लिए सही चाबी की आवश्यकता थी।

तकनीकी सारांश: $\mathbb{F}_2$ पर मैट्रिक्स-मल्टीप्लिकेशन चुनौतियों के लिए SAT प्रमाणपत्र

समस्या विवरण
यह शोध पत्र हीयूल, कौअर्स और सिडल द्वारा स्थापित मैट्रिक्स-मल्टीप्लिकेशन SAT बेंचमार्क को संबोधित करता है, जो $\mathbb{F}_2$ पर $3 \times 3$ मैट्रिक्स गुणन के लिए रैंक-23 द्विपद (bilinear) एल्गोरिदम की खोज को एनकोड करता है। यह बेंचमार्क तीन प्राथमिक चुनौती परिवारों से बना है:

चुनौती 1: दस फॉर्मूले जिन्हें 'सैटिस्फिएबल' (satisfiable) घोषित किया गया था लेकिन ऐतिहासिक रूप से सामान्य SAT सॉल्वर के लिए कठिन रहे हैं।
चुनौती 2: दस फॉर्मूले जिनमें "टाइप-3" मोनॉमियल्स (मानक मैट्रिक्स गुणन पद) के हार्डकोडेड युग्म (pairings) शामिल हैं, जिनके बारे में यह अनुमान लगाया गया था कि वे 'अनसैट' (UNSAT) होंगे।
चुनौती 3: एक एकल फॉर्मूला जो यह पूछता है कि क्या एक ऐसा रैंक-23 स्कीम अस्तित्व में हो सकता है जहाँ एक विशिष्ट समंक (summand) में शून्य टाइप-3 मोनॉमियल्स हों।

मुख्य गणितीय वस्तु $3 \times 3$ मैट्रिक्स-मल्टीप्लिकेशन टेंसर का 23 रैंक-वन समंकों में अपघटन (decomposition) है, जो 729 क्यूबिक ब्रेंट समीकरणों (Brent equations) को संतुष्ट करता है। इन समीकरणों को टसेइन (Tseitin) वेरिएबल्स के माध्यम से कंजंक्टिव नॉर्मल फॉर्म (CNF) में एनकोड किया गया है, जिसके परिणामस्वरूप 26,541 वेरिएबल्स और 2.4 मिलियन से अधिक क्लॉज़ (clauses) वाले इंस्टेंस प्राप्त होते हैं।

कार्यप्रणाली
लेखक एक "सिमेंटिक लोकल सर्च" दृष्टिकोण का उपयोग करते हैं जो पूर्ण CNF वेरिएबल्स के बजाय 621 बेस वेरिएबल्स (मैट्रिक्स $A_t, B_t, C_t$ के प्रविष्टियों) पर कार्य करता है। यह कार्यप्रणाली तीन अलग-अलग चरणों में आगे बढ़ती है:

सिमेंटिक सर्च और रेसिडुअल वॉक (Residual Walk): एल्गोरिदम एक "रेसिडुअल" टेंसर (वर्तमान रैंक-वन टेंसरों के योग और लक्ष्य टेंसर के बीच का अंतर) बनाए रखता है। यह दो-चरणीय वॉक करता है:
- डायरेक्ट रिपेयर (Direct Repair): उन बिट्स को बदलता है जो तुरंत एक विशिष्ट रेसिडुअल दोष को ठीक करते हैं।
- गेन/एक्टिवेशन (Gain/Activation): ऐसे मूव्स की अनुमति देता है जो भविष्य के कैंसिलेशन के लिए टेंसर को तैयार करने हेतु अस्थायी रूप से रेसिडुअल वेट बढ़ा सकते हैं, जिसे रेसिडुअल हैमिंग वेट में परिवर्तन ($break - make$) द्वारा स्कोर किया जाता है।
  एक बार जब सिमेंटिक रूप से ज़ीरो-रेसिडुअल अवस्था मिल जाती है, तो 621 बेस वेरिएबल्स को असाइन किया जाता है, और शेष 25,920 सहायक टसेइन वेरिएबल्स को निर्धारित करने के लिए यूनिट प्रोपेगेशन का उपयोग किया जाता है।
सिमेट्री और ट्रांसफॉर्मेशन (चुनौती 2): "अपेक्षित-UNSAT" इंस्टेंस के लिए, शोध पत्र प्रदर्शित करता है कि CNF बाधाएं केवल सकारात्मक यूनिट क्लॉज़ के माध्यम से विशिष्ट टाइप-3 घटनाओं (incidences) की उपस्थिति को लागू करती हैं, न कि अन्य की सटीक अनुपस्थिति को। साक्ष्य (witnesses) बनाने के लिए:
- लेखक ज्ञात सटीक 23-समंदंड स्कीम्स को रूपांतरित करने के लिए $GL(3, 2)^3$ आइसोट्रॉपी एक्शन का उपयोग करते हैं।
- चक्रीय ट्रेस सिमेट्री (Cyclic trace symmetry) $(A, B, C) \to (B, C, A)$ को लागू किया जाता है।
- एक परफेक्ट मैचिंग एल्गोरिदम रूपांतरित समंड्स को सकारात्मक यूनिट क्लॉज़ द्वारा परिभाषित बाधित स्लॉट्स में असाइन करता है।
लॉक्ड रिपेयर और आइडेंटिटी (चुनौती 3): टाइप-3-मुक्त समंक की स्थिति को संतुष्ट करने के लिए:
- लेखक एक सीड सॉल्यूशन से तीन विशिष्ट पदों को फिक्स करते हैं।
- $\mathbb{F}_2$ पर एक रैंक-संरक्षण पहचान (rank-preserving identity) लागू की जाती है: $92 \otimes 89 + 438 \otimes 24 = 92 \otimes 65 + 490 \otimes 24$ । यह ऑपरेशन दो समंड्स को दो अन्यों से बदलकर कुल टेंसर योग को संरक्षित रखते हुए एक समंड को पुनर्गठित करने की अनुमति देता है ताकि उसका टाइप-3 मोनॉमियल काउंट शून्य हो सके।

प्रमुख योगदान और परिणाम
शोध पत्र बेंचमार्क रिपॉजिटरी (कमिट 150b2e2f) के सभी 21 इंस्टेंस के लिए पूर्ण, स्वतंत्र रूप से सत्यापन योग्य SAT प्रमाणपत्र प्रदान करता है:

चुनौती 1: सभी 10 इंस्टेंस को सिमेंटिक लोकल सर्च का उपयोग करके हल किया गया है। समाधान सेकंडों में उत्पन्न होते हैं, जो यह दर्शाता है कि सामान्य सॉल्वरों के लिए कठिनाई टसेइन एनकोडिंग के कारण है, न कि अंतर्निहित टेंसर ज्योमेट्री के कारण।
चुनौती 2: सभी 10 इंस्टेंस, जिन्हें पहले UNSAT माना गया था, अब सैटिस्फिएबल सिद्ध हुए हैं। शोध पत्र प्रकट करता है कि "हार्डकोडेड" युग्म सटीक कोर नहीं थे; फॉर्मूले अतिरिक्त टाइप-3 घटनाओं की अनुमति देते हैं जब तक कि कुल पैरिटी सही रहे। निर्मित साक्ष्यों (witnesses) में कुल टाइप-3 घटनाएँ 41 से 93 के बीच हैं, जबकि अपेक्षित संख्या 27 थी।
चुनौती 3: एक वैध रैंक-23 अपघटन बनाया गया है जहाँ एक समंड का टाइप-3 काउंट शून्य है। यह चुनौती-3 के CNF की विशिष्ट बाधा को संतुष्ट करता है।
सत्यापन: एक अलग पार्सर और क्लॉज़ इवैल्यूएटर ने स्वतंत्र रूप से सभी 21 मॉडल्स को सत्यापित किया। सत्यापन प्रक्रिया ने शून्य विफलताओं के साथ 557,361 असाइंड वेरिएबल्स और 2,461,316 क्लॉज़ की जाँच की। एक नियत (deterministic) पायथन रिप्रोड्यूसर लगभग नौ सेकंड में सभी प्रमाणपत्रों को पुन: उत्पन्न करता है।

महत्व
इस शोध पत्र का प्राथमिक महत्व प्रदान किए गए विशिष्ट CNF फाइलों के सत्य मान (truth value) को हल करना है। यह स्थापित करता है कि:

"अपेक्षित-UNSAT" चुनौती-2 फॉर्मूले सैटिस्फिएबल हैं क्योंकि उनकी बाधाएं समावेशी (positive units) हैं, न कि अनन्य (exclusive)।
टेंसर सिमेट्री ग्रुप और सिमेंटिक संरचना ऐसे साक्ष्य (witnesses) बनाने की अनुमति देती है जिन्हें जेनेरिक CDCL सॉल्वर कुशलतापूर्वक नहीं खोज पाते हैं।
$\mathbb{F}_2$ पर एक रैंक-23 स्कीम के भीतर टाइप-3-मुक्त समंक प्राप्त करना संभव है।

यह कार्य स्पष्ट रूप से कहता है कि यह रैंक-22 प्रश्न (चुनौती 4) को हल नहीं करता है और न ही यह किसी भी रिंग पर नॉन-कम्यूटेटिव एल्गोरिदम का दावा करता है। योगदान सख्ती से प्रदान किए गए बूलियन एनकोडिंग की सैटिस्फिएबिलिटी और एक सिमेंटिक निर्माण पाइपलाइन के प्रदर्शन तक सीमित है जो इन विशिष्ट इंस्टेंस पर कच्चे SAT सॉल्विंग की सीमाओं को दरकिनार करता है। लेखक कम्प्यूटेशनल अन्वेषण के लिए OpenAI GPT-5.6 Sol के उपयोग को स्वीकार करते हैं लेकिन इस बात पर जोर देते हैं कि उनके गणितीय दावे स्वतंत्र रूप से जांच योग्य आर्टिफैक्ट्स पर आधारित हैं।

वह महान "असंभव" पहेली जो वास्तव में संभव थी

शिफ्टिंग और स्वैपिंग का जादू

"घोस्ट" ब्रिक और पूर्ण समाधान

अंतिम जाँच

इसका क्या अर्थ है (और क्या नहीं)

इसी तरह के और पेपर