तकनीकी सारांश: 3-VASS पहुँच योग्यता (Reachability) EXPSPACE में है

समस्या विवरण

यह शोध पत्र 3-आयामी वेक्टर एडिशन सिस्टम विद स्टेट्स (3-VASS) की पहुँच योग्यता (reachability) समस्या को संबोधित करता है। एक VASS, एक परिमित-अवस्था वाला ऑटोमेटा (finite-state automaton) है जो निश्चित संख्या में काउंटरों (आयामों) से लैस होता है जो गैर-ऋणात्मक पूर्णांकों (non-negative integers) को धारण करते हैं। पहुँच योग्यता समस्या यह पूछती है कि क्या एक लक्ष्य विन्यास (state और काउंटर मान) एक स्रोत विन्यास से वैध संक्रमणों (transitions) के अनुक्रम के माध्यम से सुलभ है।

जबकि सामान्य VASS पहुँच योग्यता समस्या (जहाँ आयाम इनपुट का हिस्सा है) को 2021 में ACKERMANN-complete सिद्ध किया गया था, $d > 2$ के लिए निश्चित आयामों वाले मामले में सटीक जटिलता अभी भी एक केंद्रीय खुला प्रश्न है। विशेष रूप से 3-VASS के लिए:

• लोअर बाउंड (Lower Bound): यह समस्या PSPACE-hard है, जो 2-आयामी मामले से विरासत में मिली है।
• पूर्व अपर बाउंड (Previous Upper Bound): इस कार्य तक, सबसे अच्छा ज्ञात अपर बाउंड 2-EXPSPACE (डबल-एक्सपोनेंशियल स्पेस) था, जिसे Czerwiński et al. (ICALP 2025) द्वारा स्थापित किया गया था। उससे पहले, एल्गोरिदम नॉन-एलिमेंट्री (non-elementary) थे।

इस शोध पत्र का लक्ष्य 3-VASS पहुँच योग्यता के EXPSPACE (सिंगल-एक्सपोनेंशियल स्पेस) में होने को सिद्ध करके PSPACE लोअर बाउंड और 2-EXPSPACE अपर बाउंड के बीच के अंतर को कम करना है।

कार्यप्रणाली और प्रमाण रणनीति

प्रमाण का मुख्य आधार एक 3-VASS में दो विन्यासों के बीच लघुतम रन (shortest runs) के लिए एक डबली-एक्सपोनेंशियल लंबाई सीमा स्थापित करना है। यदि लघुतम रन की लंबाई $N^{2^{poly(k)}}$ (जहाँ $N$ इनपुट आकार है और $k$ स्ट्रॉन्गली कनेक्टेड कंपोनेंट्स की संख्या है) द्वारा सीमित है, तो पहुँच योग्यता को उस लंबाई के पथ का नॉन-डिटरमिनिस्टिक अनुमान लगाकर EXPSPACE में निर्धारित किया जा सकता है।

लेखक एक श्रेणीबद्ध न्यूनीकरण रणनीति (hierarchical reduction strategy) और एक चिंताओं के पृथक्करण (separation-of-concerns) प्रमाण तकनीक का उपयोग करते हैं, जो 3-VASS के उदाहरणों को उप-वर्गों के एक अनुक्रम में परिष्कृत करती है। यह दृष्टिकोण उस "नेस्टेड" इंडक्शन (nested induction) से बचता है जिसके कारण पिछले कार्यों में ट्रिपल-एक्सपोनेंशियल बाउंड प्राप्त हुए थे।

1. VASS का श्रेणीबद्ध वर्गीकरण (Hierarchical Classification of VASS)

शोध पत्र 3-VASS के उप-वर्गों को परिभाषित करता है, जो बढ़ती व्यापकता के क्रम में हैं:
$$\text{DiagVASS}_3 \subsetneq \text{Semi-diagVASS}_3 \subsetneq \text{PumpVASS}_3 \subsetneq \text{Semi-pumpVASS}_3 \subsetneq \text{SeqVASS}_3$$

• DiagVASS: वे उदाहरण जहाँ फॉरवर्ड और बैकवर्ड दोनों "डायगोनल" चक्र (cycles) मौजूद हैं (ऐसे चक्र जो सभी काउंटरों को सकारात्मक रूप से पंप कर सकते हैं)।
• PumpVASS: उदाहरण जहाँ फॉरवर्ड और बैकवर्ड दोनों "पंप करने योग्य" चक्र (कम से कम एक काउंटर को सकारात्मक रूप से पंप करने वाले चक्र) मौजूद हैं।
• SeqVASS: सामान्य अनुक्रमिक (sequential) VASS, जहाँ रन ब्रिजों (bridges) द्वारा जुड़े स्ट्रॉन्गली कनेक्टेड कंपोनेंट्स (SCCs) के एक अनुक्रम को पार करता है।

प्रमाण सबसे अधिक प्रतिबंधात्मक वर्ग (DiagVASS) के लिए लंबाई की सीमा स्थापित करके आगे बढ़ता है और फिर इन सीमाओं को अधिक सामान्य वर्गों में स्थानांतरित करने के लिए लंबाई-नियंत्रित स्व-न्यूनीकरण (length-controlled self-reductions) का उपयोग करता है।

2. प्रमुख तकनीकी घटक

A. पहुँच सेटों का कुशल प्रतिनिधित्व (ज्यामितीय रूप से 2D VASS)

एक महत्वपूर्ण उपकरण ज्यामितीय रूप से 2-आयामी VASS का विश्लेषण है, जहाँ सभी रन दो समानांतर 2D प्लेन के बीच रहते हैं। लेखक Czerwiński et al. के परिणामों का विस्तार करते हैं ताकि यह दिखाया जा सके कि ऐसे सिस्टम का पहुँच सेट (reachability set), भले ही वह एक "हाइब्रिड सेट" (एक आधार वेक्टर प्लस एक प्रतिबंधित आवधिक सेट) से शुरू हो, हाइब्रिड सेट के एक परिमित संघ (finite union) के रूप में दर्शाया जा सकता है जिसका विवरण बहुपद-आकार (polynomial-sized) का होता है। यह प्रतिनिधित्व के आकार में एक्सपोनेंशियल वृद्धि किए बिना पहुँच सेटों के कुशल हेरफेर की अनुमति देता है।

B. गैर-वाइड डायगोनल (Non-Wide Diagonal) मामलों को संभालना

DiagVASS के लिए, लेखक "वाइड" (wide) और "गैर-वाइड" (non-wide) उदाहरणों के बीच अंतर करते हैं।

• Wide: सिस्टम का अनुक्रमिक शंकु (sequential cone) सभी सकारात्मक वेक्टरों को समाहित करता है। इन्हें ज्ञात परिणामों में बदलकर संभाला जाता है।
• Non-Wide: लेखक सिद्ध करते हैं कि गैर-वाइड डायगोनल उदाहरणों में, रन के प्रीफिक्स (prefix) और सफिक्स (suffix) के अनुक्रमिक शंकु एक हाइपरप्लेन द्वारा अलग किए गए होते हैं। यह ज्यामितीय अलगाव बताता है कि मध्यवर्ती घटकों में काउंटर मान दो समानांतर 2D प्लेन के भीतर सीमित हैं। फलस्वरूप, इस समस्या को ज्यामितीय रूप से 2-आयामी VASS के अनुक्रम में बदला जा सकता है, जिससे ऊपर वर्णित कुशल प्रतिनिधित्व तकनीकों को लागू करके डबली-एक्सपोनेंशियल बाउंड प्राप्त किया जा सकता है।

C. लंबाई-नियंत्रित स्व-न्यूनीकरण (Length-Controlled Self-Reduction)

PumpVASS और SeqVASS से DiagVASS की ओर बढ़ने के लिए, शोध पत्र एक लंबाई-नियंत्रित स्व-न्यूनीकरण पेश करता है।

• संयुक्त डायगोनैलिटी का निष्कर्षण (Extraction of Joint Diagonality): एक पंप करने योग्य उदाहरण के लिए, लेखक दिखाते हैं कि एक "संयुक्त रूप से डायगोनल" प्रीफिक्स (चक्रों का एक अनुक्रम जो सामूहिक रूप से सभी काउंटरों को पंप करता है) निकाला जा सकता है।
• न्यूनीकरण (Reduction): इस प्रीफिक्स का उपयोग कम घटकों (या सरल संरचना) वाले एक नए VASS उदाहरण के निर्माण के लिए किया जाता है जो डायगोनल है। इस नए उदाहरण का आकार लक्षित वर्ग के लंबाई फलन (length function) द्वारा नियंत्रित होता है।
• नेस्टिंग से बचना (Avoiding Nesting): पिछले दृष्टिकोणों के विपरीत, जो लंबाई बाउंड फलन को नेस्ट करते थे (जैसे, $h_k(h_{k-1}(\dots))$), यह विधि सुनिश्चित करती है कि लंबाई बाउंड रिकरेंस (recurrence) के दाहिने हाथ की ओर केवल एक बार दिखाई दे। यह संरचनात्मक परिवर्तन ही जटिलता को 2-EXPSPACE से EXPSPACE तक कम करता है।

प्रमुख योगदान और परिणाम

1. मुख्य प्रमेय (Main Theorem): 3-VASS पहुँच योग्यता समस्या EXPSPACE में है।

   • यह इनपुट के यूनरी (unary) और बाइनरी (binary) दोनों एन्कोडिंग के लिए मान्य है।
   • प्रमाण यह दिखाने पर निर्भर करता है कि किसी भी $k$-घटक 3-VASS के लिए, लघुतम रन की लंबाई $size(V, s, t)^{2^{poly(k)}}$ द्वारा सीमित है।

2. परिष्कृत जटिलता परिदृश्य (Refined Complexity Landscape): शोध पत्र 3-VASS के उप-वर्गों के जटिलता विश्लेषण प्रदान करता है:

   • DiagVASS3: EXPSPACE में सिद्ध (पिछले 2-EXPSPACE बाउंड में सुधार)।
   • PumpVASS3: डबली-एक्सपोनेंशियल रूप से छोटे रन प्रदर्शित करने के लिए सिद्ध।
   • SeqVASS3: PumpVASS में स्व-न्यूनीकरण के माध्यम से डबली-एक्सपोनेंशियल रूप से छोटे रन प्रदर्शित करने के लिए सिद्ध।

3. पद्धतिगत प्रगति (Methodological Advancement): शोध पत्र एक श्रेणीबद्ध पंपेबिलिटी विश्लेषण और चिंताओं के पृथक्करण की रणनीति पेश करता है। समस्या को ज्यामितीय रूप से 2D उप-समस्याओं में विघटित करके और ऐसे स्व-न्यूनीकरणों का उपयोग करके जो घटक पदानुक्रम (component hierarchy) का सम्मान करते हैं, लेखक पिछले इंडक्टिव प्रमाणों में निहित ट्रिपल-एक्सपोनेंशियल वृद्धि को समाप्त करते हैं।

महत्व और दावे

शोध पत्र का दावा है कि यह 3-VASS पहुँच योग्यता समस्या की समझ को महत्वपूर्ण रूप से बढ़ाता है, जो सैद्धांतिक कंप्यूटर विज्ञान में एक लंबे समय से चली आ रही चुनौती रही है।

• बाउंड को कड़ा करना (Tightening the Bound): यह परिणाम 3-VASS के लिए जटिलता अंतराल को डबल-एक्सपोनेंशियल अपर बाउंड से सिंगल-एक्सपोनेंशियल तक कम करता है। जबकि लोअर बाउंड PSPACE बना हुआ है, लेखक नोट करते हैं कि सामान्य 3-VASS से पंप करने योग्य 3-VASS में न्यूनीकरण संभवतः बहुपद स्थान (polynomial space) में नहीं किया जा सकता है, जो यह सुझाव देता है कि 3-VASS वास्तव में EXPSPACE-hard हो सकता है।
• भविष्य के कार्य के लिए आधार: शोध पत्र स्पष्ट रूप से कहता है कि सटीक जटिलता (PSPACE बनाम EXPSPACE) का निर्धारण अभी भी खुला है। यह रेखांकित करता है कि एक निश्चित EXPSPACE-हार्डनेस प्रमाण के लिए डबली-एक्सपोनेंशियल लघुतम रन वाले 3-VASS के उदाहरण की आवश्यकता होगी, जो वर्तमान में अज्ञात है।
• उच्च आयामों के लिए निहितार्थ: लेखक सुझाव देते हैं कि लघुतम रन को सीमित करने के उनके दृष्टिकोण से $d \ge 4$ आयामों वाले VASS के विश्लेषण में भी लाभ मिल सकता है, जहाँ वर्तमान अपर बाउंड्स एलिमेंट्री (elementary) से बहुत दूर हैं।

संक्षेप में, शोध पत्र एक कठोर प्रमाण प्रदान करता है कि 3-VASS पहुँच योग्यता समस्या को एक्सपोनेंशियल स्पेस में हल किया जा सकता है, जिसमें ज्यामितीय पृथक्करण तर्कों, कुशल पहुँच सेट प्रतिनिधित्वों और एक परिष्कृत स्व-न्यूनीकरण ढांचे का नवीन संयोजन उपयोग किया गया है जो पिछले तरीकों की जटिलता वृद्धि को टालता है।