💻 computer science

Towards a Doubly Efficient IP=PSPACE

यह शोधपत्र $T(n)=n^{O(\log n)}$ समय में निर्णायक योग्य PSPACE भाषाओं के लिए एक दोहरी कुशल (doubly efficient) संवादात्मक प्रमाण प्रणाली (interactive proof system) का एक काफी सरल, प्रत्यक्ष निर्माण प्रस्तुत करता है, जो बर्गर एट अल द्वारा स्थापित $n^{O(\sqrt{\log n / \log\log n}}$ के पिछले समय संबंधी मान में महत्वपूर्ण सुधार करता है।

मूल लेखक: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi

प्रकाशित 2026-06-23

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

CC BY 4.0

मूल लेखक: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi

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

यहाँ "Towards a Doubly Efficient IP = PSPACE" पेपर का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ स्पष्टीकरण दिया गया है।

बड़ी तस्वीर: "सुपर-वेरिफायर" (Super-Verifier) की समस्या

कल्पना कीजिए कि एक जादूगर (प्रूवर - Prover) ने एक बहुत लंबी और जटिल कहानी लिखी है। आप (वेरिफायर - Verifier) यह जानना चाहते हैं कि क्या वह कहानी सच है।

पुराना तरीका (Standard Interactive Proofs): अतीत में, इतनी लंबी कहानी को जाँचने के लिए, आपको उसे खुद पूरा पढ़ना पड़ता था। यदि कहानी लिखने में दस लाख साल लगे होते, तो उसे पढ़ने में भी आपको दस लाख साल लगते। यह बहुत धीमा है।
"डबली एफिशिएंट" (Doubly Efficient) लक्ष्य: इस पेपर का लक्ष्य एक ऐसा सिस्टम बनाना है जहाँ:
1. जादूगर कहानी लिखने में उचित समय ले सके (कहानी लिखने के समय से बस थोड़ा सा अधिक)।
2. आप उस प्रमाण (proof) की जाँच बहुत कम समय में कर सकें (पूरी कहानी पढ़ने की तुलना में बहुत तेज़), भले ही कहानी अविश्वसनीय रूप से लंबी हो।

लेखकों ने एक नया "जादुई करतब" (प्रोटोकॉल) बनाया है जो आपको जटिल गणनाओं को पहले से कहीं अधिक तेज़ी से सत्यापित करने की अनुमति देता है, जिससे संभावनाओं की सीमाओं को आगे बढ़ाया जा सकता है।

मुख्य चुनौती: "लंबी यात्रा" (The Long Journey)

एक कंप्यूटर गणना को एक लंबी यात्रा के रूप में सोचें।

शुरुआत: कंप्यूटर एक विशिष्ट बिंदु (कॉन्फ़िगरेशन A) से शुरू होता है।
अंत: वह एक विशिष्ट बिंदु (कॉन्फ़िगरेशन B) पर समाप्त होता है।
यात्रा: A से B तक पहुँचने के लिए, कंप्यूटर $T$ कदम उठाता है। यदि $T$ बहुत बड़ा है (जैसे $n^{\log n}$ ), तो हर एक कदम की जाँच करना एक मानव-स्तर के वेरिफायर के लिए असंभव है।

पिछली रणनीति (The "Batching" Trap):
इस पेपर से पहले, शोधकर्ताओं ने इसे कई यात्राओं को एक साथ जोड़कर हल करने की कोशिश की थी। कल्पना कीजिए कि आपके पास 1,000 अलग-अलग यात्राएँ हैं जिन्हें जाँचना है।

वे कहते थे, "आइए सभी 1,000 यात्राओं को एक साथ जाँचते हैं!"
उन्होंने एक जटिल, अप्रत्यक्ष विधि का उपयोग किया: पहले, उन्होंने एक उपकरण बनाया जो एक यात्रा को पूरी तरह से जाँच सके। फिर, उन्होंने उस उपकरण को 1,000 यात्राओं को जाँचने के लिए एक "ब्लैक बॉक्स" के रूप में उपयोग करने की कोशिश की।
समस्या: यह "ब्लैक बॉक्स" दृष्टिकोण कार के टायर देखकर इंजन ठीक करने की कोशिश करने जैसा था। यह काम तो करता था, लेकिन यह बोझिल, जटिल था और एक ऐसी दीवार से टकरा गया जहाँ यह और तेज़ नहीं हो सकता था।

नई रणनीति (The "Direct Route"):
यह पेपर कहता है, "आइए ब्लैक बॉक्स का उपयोग करना बंद करें। आइए सीधे इंजन को देखें।"
अलग-अलग 1,000 यात्राओं को जाँचने या उन्हें जटिल समूह में जाँचने के बजाय, वे एक ही बार में सभी यात्राओं के पूरे मानचित्र (map) को देखते हैं और एक शॉर्टकट ढूँढते हैं।

जादुई करतब: "मिडपॉइंट मैट्रिक्स" (Midpoint Matrix) और "चेकसम" (Checksum)

यहाँ बताया गया है कि उनका नया प्रोटोकॉल कैसे काम करता है, एक हाइकिंग ट्रिप (पदयात्रा) के उदाहरण के साथ।

1. सेटअप: हाइकिंग मैप

कल्पना कीजिए कि आप दावा करते हैं कि आपने बेस कैंप से शिखर तक एक विशाल पर्वत श्रृंखला की पदयात्रा की है।

पुराना तरीका: आप मुझे हर एक कदम की फोटो भेजते हैं। मुझे लाखों फोटो देखनी पड़ती हैं।
नया तरीका: आप मुझे सारी फोटो नहीं भेजते। इसके बजाय, आप मुझे कुछ विशिष्ट "चेकपॉइंट्स" के साथ एक मैप (नक्शा) भेजते हैं।

2. "मिडपॉइंट मैट्रिक्स" (चेकपॉइंट्स का ग्रिड)

लेखक एक विशाल ग्रिड (मैट्रिक्स) के रूप में प्रमाण की कल्पना करते हैं।

पंक्तियाँ (Rows): प्रत्येक पंक्ति एक अलग हाइकिंग ट्रिप (या गणना का एक अलग हिस्सा) है।
स्तंभ (Columns): प्रत्येक स्तंभ समय का एक विशिष्ट क्षण है।
इसके बजाय पूरा ग्रिड भेजने के बजाय, प्रूवर एक चेकसम (Checksum) भेजता है।

उदाहरण: कल्पना कीजिए कि आपके पास 1,000 हाइकिंग लॉग्स (डायरी) का एक ढेर है। उन्हें पढ़ने के बजाय, आप उन्हें एक विशेष मशीन से गुजारते हैं जो पूरे ढेर के लिए एक एकल "फिंगरप्रिंट" (चेकसम) प्रिंट करती है। यदि लॉग्स नकली हैं, तो फिंगरप्रिंट गलत होगा। यह प्रूवर को एक विशिष्ट सेट के लॉग्स के प्रति प्रतिबद्ध होने के लिए मजबूर करता; वे बाद में उन्हें बदल नहीं सकते।

3. "रो-आईपीपी" (The Row-IPP - रैंडम स्पॉट चेक)

यही सबसे चतुर हिस्सा है। वेरिफायर (आप) पूरा ग्रिड नहीं पढ़ता।

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

"जीत-हार" का तर्क (Win-Win Logic):
यह पेपर तर्क देता है कि प्रूवर एक ऐसी स्थिति में है जहाँ वह जीत नहीं सकता:

परिदृश्य A: प्रूवर पूरे मैप के बारे में झूठ बोलने की कोशिश करता है। "फिंगरप्रिंट" (चेकसम) तुरंत झूठ को पकड़ लेता है क्योंकि मैप सच्चाई से बहुत दूर है।
परिदृश्य B: प्रूवर केवल थोड़ा सा झूठ बोलने की कोशिश करता है। प्रोटोकॉल उन्हें मैप के एक विशिष्ट संस्करण के प्रति प्रतिबद्ध होने के लिए मजबूर करता है। लेकिन फिर, प्रोटोकॉल समस्या को केवल कुछ पंक्तियों की जाँच करने में बदल देता है। यदि वे कुछ पंक्तियाँ नकली हैं, तो पूरा प्रमाण विफल हो जाता है।

4. रिकर्सिव शॉर्टकट (The "Russian Doll")

यह प्रोटोकॉल केवल एक बार नहीं करता। यह रिकर्सिव तरीके से करता है, जैसे रूसी गुड़िया (Russian nesting dolls) का सेट।

यह बड़ी समस्या को छोटे टुकड़ों में तोड़ता है।
यह "फिंगरप्रिंट" और "स्पॉट चेक" पद्धति का उपयोग करके उन टुकड़ों की जाँच करता है।
यह टुकड़ों की संख्या को तब तक कम करता रहता है जब तक कि आप केवल एक बहुत छोटे, आसानी से सत्यापित किए जाने वाले हिस्से तक नहीं पहुँच जाते।

चूंकि वे यह सीधे (पिछले पत्रों में उपयोग किए गए बोझिल "ब्लैक बॉक्स" चरण के बिना) करते हैं, इसलिए वे बहुत बड़े, अधिक जटिल समस्याओं को संभाल सकते हैं।

यह क्यों महत्वपूर्ण है (द स्पीड लिमिट ब्रेकथ्रू)

यह पेपर दावा करता है कि इसने एक गति की बाधा को तोड़ दिया है।

पिछला रिकॉर्ड: सबसे तेज़ तरीका जो इन लंबी कहानियों को सत्यापित करता था, वह उन कहानियों के लिए काम करता था जिन्हें लिखने में लगभग $n^{\sqrt{\log n}}$ समय लगता था।
नया रिकॉर्ड: यह नई विधि उन कहानियों के लिए काम करती है जिन्हें लिखने में $n^{\log n}$ समय लगता है।

उदाहरण:
कल्पना कीजिए कि आप एक लाइब्रेरी की किताबों को सत्यापित करने की कोशिश कर रहे हैं।

पुराना तरीका केवल उन किताबों को सत्यापित कर सकता था जो लगभग 100 पन्नों की थीं (भले ही लाइब्रेरी बहुत बड़ी हो)।
यह नई विधि 1,000 पन्नों की किताबों को सत्यापित कर सकती है, और यह उतनी ही तेज़ी से करती है जितनी तेज़ी से 100 पन्नों की किताब की जाँच की जाती है।

"सीक्रेट सॉस" (Secret Sauce) का सारांश

प्रत्यक्ष निर्माण (Direct Construction): उन्होंने जटिल, अप्रत्यक्ष उपकरणों (ब्लैक बॉक्स) का उपयोग करना बंद कर दिया और इस काम के लिए विशेष रूप से ज़ीरो से सत्यापन उपकरण बनाया।
चेकसम कमिटमेंट (The Checksum Commitment): वे प्रोवर को जाँच शुरू करने से पहले अपनी कहानी को एक गणितीय "फिंगरप्रिंट" का उपयोग करके लॉक करने के लिए मजबूर करते हैं।
ग्रिड रिडक्शन (The Grid Reduction): वे एक विशाल, असंभव-से-जाँचने योग्य डेटा ग्रिड को जाँचने योग्य यादृच्छिक (random) पंक्तियों की एक छोटी सूची में बदल देते हैं।
सरलता (Simplicity): लेखक नोट करते हैं कि उनकी विधि पिछले तरीकों की तुलना में वास्तव में सरल है, जो इस क्षेत्र में दुर्लभ है। आमतौर पर, चीज़ों को तेज़ बनाने से वे अधिक जटिल हो जाती हैं। यहाँ, उन्होंने इसे तेज़ और सरल दोनों बनाया।

निचोड़ (The Bottom Line)

यह पेपर यह सिद्ध करने का एक नया, सरल और तेज़ तरीका पेश करता है कि कंप्यूटर ने एक बहुत लंबी गणना सही ढंग से की है। यह एक इंसान (या एक छोटे कंप्यूटर) को एक विशाल गणना को बहुत कम समय में सत्यापित करने की अनुमति देता है, जिससे कंप्यूटर विज्ञान में हमारी समझ की सीमाओं को आगे बढ़ाया जा सकता है।

तकनीकी सारांश: एक दोहरी कुशल IP = PSPACE की ओर

1. समस्या विवरण (Problem Statement)

यह शोध पत्र PSPACE में भाषाओं के लिए दोहरी कुशल इंटरैक्टिव प्रूफ (IP) सिस्टम के निर्माण को संबोधित करता है। ऐसे सिस्टम में, एक प्रूवर (जिसके पास समस्या को हल करने की गणनात्मक शक्ति होती है) और एक वेरीफायर (जिसके पास सीमित संसाधन होते हैं) गणना की शुद्धता के बारे में वेरीफायर को समझाने के लिए परस्पर क्रिया (interact) करते हैं।

विशिष्ट चुनौती ऐसी गणनाओं के लिए इसे प्राप्त करना है जो समय $T(n)$ और स्थान $S(n)$ में चलती हैं, जहाँ:

प्रूवर का रनटाइम गणना के समय का बहुपद (polynomial) है, अर्थात $\text{poly}(T(n))$ ।
वेरीफायर का रनटाइम $T(n)$ में काफी कम (sublinear) है, आदर्श रूप से इनपुट आकार $n$ का बहुपद (या $T$ के एक सबलीनियर फंक्शन और $S$ के बहुपद के रूप में) है।

इस कार्य से पहले, दोहरी कुशल IP के लिए सबसे अच्छा ज्ञात शासन (regime) $T(n) = n^{O(\sqrt{\log n / \log \log n})}$ की समय जटिलताओं (complexity) को कवर करता था (बर्जर, गोयल, होंग और कलई, 2025 द्वारा स्थापित)। लक्ष्य इस शासन को $T(n) = n^{O(\log n)}$ तक विस्तारित करना है, जो PSPACE गणनाओं के एक व्यापक वर्ग को कवर करता है।

2. कार्यप्रणाली (Methodology)

लेखक एक दोहरी कुशल IP का प्रत्यक्ष निर्माण (direct construction) प्रस्तावित करते हैं, जो पिछले कार्यों (RRR16, BGHK25) में उपयोग किए गए अप्रत्यक्ष "ब्लैक-बॉक्स" दृष्टिकोण से भिन्न है। पिछले तरीकों ने पहले अस्पष्ट (unambiguous) इंटरैक्टिव प्रमाणों के लिए बैच इंटरैक्टिव प्रूफ बनाए और फिर उन्हें एक सबरूटीन के रूप में उपयोग किया। लेखक तर्क देते हैं कि यह अप्रत्यक्ष मार्ग बाधाओं (विशेष रूप से एक "रेट-1" बैच IP की आवश्यकता) का सामना करता है और वैचारिक रूप से जटिल है।

इसके बजाय, यह शोध पत्र एक प्रोटोकॉल का निर्माण करता है जो प्रत्यक्ष रूप से नियत समय-स्थान सीमाबद्ध (deterministic time-space bounded - TISP) गणनाओं को बैच करता है। मुख्य कार्यप्रणाली एक पुनरावर्ती (recursive) प्रोटोकॉल है, जिसे Batch( $t, k$ ) कहा जाता है, जो समय- $t$ की $k$ कथनों (statements) को सत्यापित करता है।

मुख्य तकनीकी घटक (Key Technical Ingredients)

मिडपॉइंट एक्सपेंशन और मैट्रिक्स प्रतिनिधित्व (Midpoint Expansion and Matrix Representation):
वेरिफिकेशन समय $t$ को कम करने के लिए, प्रूवर प्रत्येक $k$ गणना पथों के लिए $\lambda$ मध्यवर्ती विन्यास (intermediate configurations/midpoints) भेजता है। इन्हें एक $k \times \lambda$ मैट्रिक्स $M$ में व्यवस्थित किया जाता है, जहाँ प्रत्येक पंक्ति एक गणना के विन्यासों के अनुक्रम का प्रतिनिधित्व करती है। यह $t$ समय के $k$ कथनों को $t/\lambda$ समय के $k \cdot \lambda$ कथनों में बदल देता है।
यूनिक-डिकोडिंग चेकसम्स (Unique-Decoding Checksums):
प्रूवर को बिना पकड़े गए मैट्रिक्स $M$ के असंगत या दुर्भावनापूर्ण मध्यवर्ती विन्यास भेजने से रोकने के लिए, प्रूवर मैट्रिक्स $M$ के कॉलम के चेकसम्स ( $\chi$ ) भेजता है। ये चेकसम्स लीनियर एरर-करेक्टिंग कोड्स (विशेष रूप से रीड-सोलोमन कोड्स) के साथ यूनिक-डिकोडिंग रेडियस $d$ के साथ प्राप्त किए जाते हैं। यह सुनिश्चित करता है कि यदि प्रूवर "सच्चे" विटनेस (witness) से $d$ पंक्तियों से अधिक विचलित होता है, तो चेकसम्स मेल नहीं खाएंगे।
रो-रिडक्शन के साथ इंटरैक्टिव प्रूफ ऑफ प्रॉक्सिमिटी (Row-IPP):
प्रोटोकॉल एक सामान्यीकृत इंटरैक्टिव प्रूफ ऑफ प्रॉक्सिमिटी (IPP) का उपयोग करता है जो मैट्रिसेस पर कार्य करता है। पूरे मैट्रिक्स $M$ को सत्यापित करने के बजाय, वेरीफायर Row-IPP का उपयोग यह जांचने के लिए करता है कि क्या $M$ एक विशिष्ट लो-डेप्थ प्रेडिकेट $\Phi_{reduce}$ को संतुष्ट करने के "निकट" (row-distance में) है।
- प्रेडिकेट $\Phi_{reduce}$ $Φ_{r e d u ce}$ तीन स्थितियों की जाँच करता है:
  1. मैट्रिक्स $M$ चेकसम्स $\chi$ के साथ सुसंगत है।
  2. विस्तारित बैच के कथन (जो $M$ से प्राप्त होते हैं) पुनरावर्ती दावे $\Psi_{\uparrow}$ (एक सब-प्रोटोकॉल से) को संतुष्ट करते हैं।
  3. मैट्रिक्स एक सहायक प्रेडिकेट $\Phi$ को संतुष्ट करता है।
- यदि मैट्रिक्स इन स्थितियों को संतुष्ट करने से दूर है, तो Row-IPP वेरीफायर को पंक्तियों के एक छोटे उपसमुच्चय $Q$ (आकार $\approx k/d$ ) और एक लो-डेप्थ प्रेडिकेट $\Psi_{IPP}$ को नमूना लेने की अनुमति देता है ताकि वेरीफायर को केवल सब-मैट्रिक्स $M[Q, :]$ की जाँच करनी पड़े।
पुनरावर्ती कमी (The "Win-Win" Argument):
प्रोटोकॉल दो आयामों में समस्या के आकार को पुनरावर्ती रूप से कम करता है:
- समय को कम करना ( $t$ ): मिडपॉइंट्स का विस्तार करके, प्रति कथन समय $t$ से घटकर $t/\lambda$ हो जाता है, लेकिन कथनों की संख्या बढ़कर $k \cdot \lambda$ हो जाती है।
- बैच आकार को कम करना ( $k$ ): Row-IPP लागू करके, कथनों की संख्या $k$ से घटकर $k/d$ हो जाती है (जहाँ $d$ डिस्टेंस पैरामीटर है), जबकि समय $t$ समान रहता है।
पुनरावृत्ति तब तक जारी रहती है जब तक कि या तो समय $t$ GKR प्रोटोकॉल (गोल्डवासर, कलई, रोथब्लम, 2015) के लिए पर्याप्त छोटा न हो जाए या बैच आकार $k$ इतना छोटा न हो जाए कि उसे स्पष्ट रूप से संभाला जा सके।

प्रोटोकॉल प्रवाह (Protocol Flow (Batch( $t, k$ )))

चेकसम्स: प्रूवर मिडपॉइंट मैट्रिक्स $M$ के कॉलम चेकसम्स भेजता है।
समय कमी (पुनरावर्ती कॉल 1): पक्षकार $M$ से प्राप्त विस्तारित बैच के कथनों पर Batch( $t/\lambda, k \cdot \lambda$ ) चलाते हैं। इससे एक प्रेडिकेट $\Psi_{\uparrow}$ प्राप्त होता है जिसे विस्तारित कथनों के लिए सत्य होना चाहिए।
Row-IPP: पक्षकार यह सत्यापित करने के लिए Row-IPP चलाते हैं कि क्या $M$ , (a) चेकसम्स के साथ निरंतरता, (b) $\Psi_{\uparrow}$ की संतुष्टि, और (c) वर्तमान सहायक प्रेडिकेट $\Phi$ के संयोजन के "निकट" है। यह पंक्तियों का एक उपसमुच्चय $Q$ और एक प्रेडिकेट $\Psi_{IPP}$ आउटपुट करता है।
बैच कमी (पुनरावर्ती कॉल 2): पक्षकार पंक्तियों $Q$ के संगत कथनों के कम किए गए सेट पर Batch( $t, k/d$ ) चलाते हैं, यह सत्यापित करते हुए कि वे $\Psi_{IPP}$ को संतुष्ट करते हैं।

3. मुख्य योगदान (Key Contributions)

दोहरी कुशल IP के लिए विस्तारित शासन (Extended Regime):
यह शोध पत्र किसी भी भाषा के लिए एक दोहरी कुशल IP का निर्माण करता है जो बहुपद स्थान (polynomial space) और समय $T(n) = n^{O(\log n)}$ में गणनीय है।
- प्रूवर रनटाइम: $\text{poly}(T)$ ।
- वेरीफायर रनटाइम: $\text{poly}(S, 2^{\sqrt{\log T}})$ ।
- विशेष रूप से, $T = n^{O(\log n)}$ के लिए, वेरीफायर का रनटाइम $\text{poly}(n)$ है।
प्रत्यक्ष निर्माण (Direct Construction):
लेखक TISP गणनाओं को बैच करने के लिए एक प्रत्यक्ष निर्माण प्रदान करते हैं, जो अस्पष्ट इंटरैक्टिव प्रमाणों को बैच करने वाले अप्रत्यक्ष चरणों से बचता है। यह उनके प्रत्यक्ष दृष्टिकोण को सरल बनाता है और ब्लैक-बॉक्स बैच अस्पष्ट IP पर उनकी निर्भरता को हटाता है, जो लेखकों के अनुसार कि वे "रेट-1" बैच IP की कठिनाई के कारण बाधाओं के अधीन हैं।
सरलीकृत विश्लेषण (Simplified Analysis):
प्रोटोकॉल की पुनरावर्ती संरचना का विश्लेषण कैटलन संख्याओं (Catalan numbers) पर आधारित एक पुनरावृत्ति वृक्ष (recurrence tree) का उपयोग करके किया जाता है। लेखक प्रदर्शित करते हैं कि विभाजन पैरामीटर $\lambda = 2^{\sqrt{\log T}}$ सेट करके, वेरीफायर की जटिलता को $2^{O(\sqrt{\log T})} \cdot \text{poly}(S)$ तक अनुकूलित किया जाता है।

4. परिणाम (Results)

मुख्य औपचारिक परिणाम थ्योरम 2 (और विशिष्ट मामले के लिए कोरोलरी 1) में दिया गया है:

थ्योरम: प्रत्येक भाषा के लिए एक इंटरैक्टिव प्रूफ मौजूद है जो $\text{TISP}(T, S)$ में है, जहाँ:
- प्रूवर $\text{poly}(T, S)$ समय में चलता है।
- वेरीफायर $2^{O(\sqrt{\log T})} \cdot S^2 \cdot \text{poly}(\sigma, \log S)$ समय में चलता है, जहाँ $\sigma$ साउंडनेस पैरामीटर है।
- संचार जटिलता (communication complexity) $2^{O(\sqrt{\log T})} \cdot S \cdot \text{poly}(\sigma, \log S)$ है।
निहितार्थ: $T(n) = n^{O(\log n)}$ (जिसमें PSPACE का एक महत्वपूर्ण हिस्सा शामिल है) में निर्णय योग्य भाषाओं के लिए, वेरीफायर $\text{poly}(n)$ समय में चलता है।

5. महत्व और दावे (Significance and Claims)

शोध पत्र दावा करता है कि यह कार्य अत्याधुनिक (state-of-the-art) से एक महत्वपूर्ण सुधार है:

रेंज में सुधार: यह समय जटिलता शासन को $T(n) = n^{O(\sqrt{\log n / \log \log n})}$ से बढ़ाकर $T(n) = n^{O(\log n)}$ तक विस्तारित करता है।
वैचारिक सरलता: प्रत्यक्ष निर्माण को "काफी सरल" बताया गया है। लेखक तर्क देते हैं कि पिछले तरीके, जो ब्लैक-बॉक्स बैच अस्पष्ट IP पर निर्भर थे, एक "रेट-1" बैच IP की आवश्यकता वाली बाधा से टकराते हैं। ऐसे रेट-1 IP का निर्माण चुनौतीपूर्ण माना जाता है।
भविष्य की क्षमता: लेखक तर्क देते हैं कि उनका प्रत्यक्ष दृष्टिकोण "भविष्य के सुधारों के लिए एक अधिक आशाजनक मार्ग" की ओर संकेत करता है, जिससे पता चलता है कि ब्लैक-बॉक्स अस्पष्ट IP दृष्टिकोण में निहित बाधाओं को पार करने के बजाय प्रत्यक्ष रूप से TISP गणनाओं को बैच करने को परिष्कृत करके और अधिक अनुकूलन संभव हो सकते हैं।

यह कार्य मानक क्रिप्टोग्राफिक और जटिलता-सैद्धांतिक प्रिमिटिव्स (फिनिट फील्ड्स, रीड-सोलोमन कोड्स, GKR प्रोटोकॉल, Row-IPP) पर निर्भर करता है लेकिन एक नवीन पुनरावर्ती ढांचे के भीतर उन्हें एक नया रूप देता है।