सबक्वाड्रेटिक 3SUM और सबक्यूबिक APSP

हम 3SUM और ऑल-पेयर्स शॉर्टेस्ट पाथ्स (APSP) के लिए पाठ्यपुस्तक एल्गोरिदम पर पहला बहुपद सुधार देते हैं: हम दिखाते हैं कि बहुपद आकार के n पूर्णांकों पर 3SUM को नियतात्मक रूप से O(n^{1.9992}) समय में और बहुपद रूप से बद्ध पूर्णांक भार वाले निर्देशित n-शीर्ष ग्राफ़ पर APSP को O(n^{2.9995}) समय में हल किया जा सकता है। यह 3SUM और APSP परिकल्पनाओं का खंडन करता है। ज्ञात कटौतियों का उपयोग करके, हम 3SUM और APSP परिकल्पनाओं के वास्तविक-मूल्यवान संस्करणों, एक्सेक्ट ट्राएंगल परिकल्पना, जीरो-वेट k-क्लिक परिकल्पनाओं, और van den Brand, Nanongkai, और Saranurak के तीन आयताकार संकेतित ऑनलाइन मैट्रिक्स-वेक्टर अनुमानों का भी खंडन करते हैं, और विभिन्न अन्य समस्याओं के लिए बहुपद गति प्रदान करते हैं। ये सभी परिणाम पतली मैट्रिक्स उत्पादों के लिए एक नए एल्गोरिदम से अनुसरण करते हैं। मान लीजिए X एक N×D पूर्णांक मैट्रिक्स है और Y एक D×N पूर्णांक मैट्रिक्स है जिसमें D ≤ N^{1/18} है, और W अधिकतम N^2/√D स्थितियों का कोई सेट है। हम प्रविष्टियाँ (XY)[I, J], (I, J)∈W, की गणना O(N^2/D^{0.063}) संक्रियाओं में करते हैं, जो XY लिखने या N^2/√D आंतरिक उत्पादों की एक-एक करके गणना करने के लिए आवश्यक समय से बहुपद रूप से कम है। हम इस एल्गोरिदम को Coppersmith के आयताकार मैट्रिक्स गुणन एल्गोरिदम के एक प्रकार को संशोधित करके डिज़ाइन करते हैं, जो Schönhage की दस-गुणन पहचान से निर्मित है, ताकि W में प्रविष्टियों के लिए केवल आवश्यक संक्रियाएँ की जा सकें, और दिखाते हैं कि कुछ संक्रियाएँ आवश्यक हैं। ग्राफ एल्गोरिदम के रूप में व्याख्या करने पर, यह स्पार्स लोप्साइडेड ट्राइपार्टाइट ग्राफ़ पर ऑल-एजेस स्पार्स ट्राएंगल समस्या को वास्तविक सबक्वाड्रेटिक समय में हल करता है, जहाँ दो भागों में n शीर्ष होते हैं लेकिन एक भाग में n^{ε} शीर्ष होते हैं ε<0.12 के लिए। ज्ञात कटौतियों द्वारा, एक्सेक्ट ट्राएंगल, और इसलिए 3SUM और APSP, इस समस्या में कम हो जाते हैं। हम एक डेटा संरचना संस्करण भी देते हैं जो XY की एकल प्रविष्टियों के लिए प्रश्नों का उत्तर देता है, जो पहले से ज्ञात नहीं हैं। सबमिशन इतिहास: Josh Alman से [ईमेल देखें] [v1]सोम, 5 अक्टूबर 2026 17:44:29 UTC (93 KB)

स्रोत: Hacker News · HeadlinesBriefing द्वारा सारांशित