💻 computer science

The blue pebbling cost and the space in tree-like and negative Resolution

यह शोध पत्र 'ब्लू पेबलिंग कॉस्ट' (blue pebbling cost) को प्रस्तुत करता है, जो एक नया मीट्रिक है जो ट्री-लाइक (tree-like) और नेगेटिव रेज़ोल्यूशन (negative Resolution) में क्लॉज स्पेस आवश्यकताओं को सटीक रूप से अभिलक्षित करता है, विशिष्ट फॉर्मूला वर्गों के लिए सटीक स्पेस बाउंड्स को सक्षम बनाता है और इन दो प्रूफ़ सिस्टमों के बीच एक महत्वपूर्ण स्पेस सेपरेशन प्रदर्शित करता है।

मूल लेखक: Lisa-Marie Jaser, Jacobo Torán

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

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

CC BY 4.0

मूल लेखक: Lisa-Marie Jaser, Jacobo Torán

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

कल्पना कीजिए कि आप एक विशाल, असंभव पहेली को हल करने की कोशिश कर रहे हैं। आपके पास सुरागों का एक डिब्बा है, लेकिन डिब्बा इतना छोटा है कि उसमें सभी सुराग एक साथ नहीं आ सकते। हर बार जब आप एक नया सुराग उठाते हैं, तो आपको जगह बनाने के लिए एक पुराना सुराग वापस शेल्फ पर रखना पड़ता है। सवाल यह है: पहेली को बिना अटके हल करने के लिए आपको न्यूनतम कितने आकार के डिब्बे की आवश्यकता है? यह 'प्रूफ कॉम्प्लेक्सिटी' (proof complexity) नामक एक क्षेत्र का मूल है, जहाँ गणितज्ञ और कंप्यूटर वैज्ञानिक इस बात का अध्ययन करते हैं कि किसी कथन को सत्य या असत्य सिद्ध करने के लिए कितने "मानसिक स्थान" या मेमोरी की आवश्यकता होती है।

इसे समझने के लिए, एक मानचित्र (ग्राफ) पर खेले जाने वाले खेल की कल्पना करें जिसमें केवल एकतरफा सड़कें हैं। आपके पास श्रमिकों की एक टीम (पेबल्स/कंकड़) है जिन्हें मानचित्र के शुरुआती बिंदु से अंतिम रेखा तक एक भारी क्रेट ले जाने की आवश्यकता है। नियम सख्त हैं: आप क्रेट को किसी नए स्थान पर तभी ले जा सकते हैं जब उस स्थान की ओर जाने वाली सभी सड़कें पहले से ही खाली हों या वहां कोई मौजूद हो। इस खेल की "लागत" (cost) वह संख्या है जितने श्रमिकों को काम पूरा करने के लिए एक ही समय में मानचित्र पर होना आवश्यक है। दशकों से, वैज्ञानिक तर्क पहेलियों को हल करने की कठिनाई को मापने के लिए इस खेल के विभिन्न संस्करणों का उपयोग करते आए हैं। कुछ संस्करण बहुत सख्त हैं, जिनमें श्रमिकों को एक पूर्ण, प्रतिवर्ती (reversible) क्रम में रखा और हटाया जाना चाहिए। अन्य संस्करण अधिक लचीले हैं, जो श्रमिकों को अधिक स्वतंत्र रूप से इधर-उधर ले जाने की अनुमति देते हैं। आप जो पेपर पढ़ने जा रहे हैं, वह इस खेल को खेलने का एक बिल्कुल नया तरीका पेश करता है, जो इन सख्त और लचीले नियमों के ठीक बीच में स्थित है, और इसका उपयोग यह जांचने के लिए किया जाता है कि तार्किक प्रमाणों (logical proofs) की जाँच करने के लिए कंप्यूटरों को कितनी मेमोरी स्पेस की आवश्यकता होती है।

द ब्लू पेबल: गिनने का एक नया तरीका

लेखक, लिसा-मैरी जेसर और जैकोबो टोरान, क्लासिक "पेबल गेम" में एक नया मोड़ पेश करते हैं। पारंपरिक संस्करण में, आप बस बोर्ड पर मौजूद पेबल्स की गिनती करते हैं। लेकिन उनके नए संस्करण में, "रेड-ब्लू" गेम में, पेबल्स दो रंगों के होते हैं: लाल और नीला। खेल तब समाप्त होता है जब एक विशिष्ट स्थिति पूरी हो जाती है, लेकिन यहाँ मुख्य बात यह है: खेल की लागत उपयोग किए गए कुल पेबल्स की संख्या नहीं है। इसके बजाय, लागत केवल वह संख्या है जो खेल के दौरान नीले पेबल्स के रूप में दिखाई देती है।

इसे एक वीडियो गेम की तरह समझें जहाँ आपके पास असीमित मात्रा में "मुफ्त" लाल टोकन हैं, लेकिन हर "नीले" टोकन के लिए आपको एक जीवन (life) खोना पड़ता है। लक्ष्य कम से कम जीवन (नीले टोकन) खोते हुए फिनिश लाइन तक पहुँचना है। लेखक सिद्ध करते हैं कि यह "ब्लू कॉस्ट" (नीला खर्च) ट्री-लाइक रेज़ोल्यूशन (Tree-like Resolution) नामक एक विशिष्ट प्रकार के तार्किक प्रमाण के लिए आवश्यक मेमोरी स्पेस को मापने के लिए एक आदर्श पैमाना है।

तर्क की दुनिया में, एक "रेज़ोल्यूशन" प्रमाण एक तर्क की श्रृंखला की तरह है जहाँ आप दो कथनों को मिलाकर एक नया कथन बनाते हैं, जो अंततः एक विरोधाभास (मूल विचार को गलत साबित करना) की ओर ले जाता है। "ट्री-लाइक" प्रमाणों में, तर्क की श्रृंखला एक पेड़ की तरह दिखती है: आप किसी शाखा का पुन: उपयोग नहीं कर सकते; यदि आपको किसी हिस्से की फिर से आवश्यकता है, तो आपको उसे शुरुआत से बनाना होगा। यह काफी हद तक उस DPLL एल्गोरिदम के समान है जिसका उपयोग कंप्यूटर प्रोग्रामों में तर्क पहेलियों को हल करने के लिए किया जाता है (SAT सॉल्वर)।

पेपर दिखाता है कि किसी भी असंभव तार्किक पहेली के लिए, ट्री-लाइक रेज़ोल्यूशन का उपयोग करके उसे हल करने के लिए आवश्यक न्यूनतम मेमोरी स्पेस, पहेली के मानचित्र पर गेम जीतने के लिए आवश्यक न्यूनतम नीले पेबल्स की संख्या के ठीक बराबर है। इससे पहले, वैज्ञानिक केवल यह कह सकते थे कि मेमोरी स्पेस एक अलग, सख्त गेम (रिवर्सिबल गेम) से एक लॉगरिदमिक कारक (logarithmic factor) से संबंधित है, लेकिन वह थोड़ा अलग था। नया "ब्लू पेबल" माप इस अंतर को ठीक करता है, जिससे एक सटीक, एक-से-एक मिलान प्राप्त होता है। यह अंततः सही चाबी खोजने जैसा है जो ताले में पूरी तरह फिट बैठती है, न कि ऐसी चाबी जो लगभग काम करती है।

तर्क का रंग: OR बनाम XOR

शोधकर्ताओं ने यहीं नहीं रोका। उन्होंने अपने नए ब्लू पेबल पैमाने का परीक्षण दो प्रसिद्ध प्रकार के "लिफ्टेड" (lifted) तर्क पहेलियों पर किया। ये वे पहेलियाँ हैं जहाँ साधारण वेरिएबल्स को अधिक जटिल मिनी-फॉर्मूला से बदल दिया जाता है, जिससे पूरी चीज़ को हल करना बहुत कठिन हो जाता है।

"OR" पहेलियाँ (PebG[∨]): इन पहेलियों में, वेरिएबल्स को एक "OR" फंक्शन (यदि A या B सत्य है, तो परिणाम सत्य है) द्वारा बदल दिया जाता है। लेखकों ने पाया कि ट्री-लाइक रेज़ोल्यूशन में इन्हें हल करने के लिए आवश्यक मेमोरी स्पेस, अंतर्निहित मानचित्र के ब्लू पेबल खर्च की दर के समान ही बढ़ता है।
"XOR" पहेलियाँ (PebG[⊕]): यहाँ, वेरिएबल्स को एक "XOR" फंक्शन (परिणाम सत्य है केवल तभी जब ठीक एक ही A या B सत्य हो) द्वारा बदला जाता है। इनके लिए, मेमोरी स्पेस अलग तरह से व्यवहार करता है, जो "रिवर्सिबल" पेबल लागत से मेल खाता है।

यह अंतर महत्वपूर्ण है क्योंकि यह दिखाता है कि तर्क का "रूप" (OR बनाम XOR) यह बदल देता है कि कितनी मेमोरी की आवश्यकता होती है, और ब्लू पेबल गेम वह उपकरण है जो OR संस्करण के लिए लागत को सही ढंग से पहचानता है।

महान स्पेस सेपरेशन (The Great Space Separation)

इस पेपर की सबसे आश्चर्यजनक खोज शायद दो अलग-अलग तरीकों से समस्याओं को हल करने के बीच का "स्पेस सेपरेशन" है: ट्री-लाइक रेज़ोल्यूशन और नेगेटिव रेज़ोल्यूशन।

"नेगेटिव रेज़ोल्यूशन" में, एक विशेष नियम है: हर बार जब आप दो कथनों को मिलाते हैं, तो उनमें से एक पूरी तरह से नकारात्मक शब्दों (जैसे "not A," "not B") से बना होना चाहिए। आप सोच सकते हैं कि यदि एक विधि (नेगेटिव रेज़ोल्यूशन) दूसरी विधि (ट्री-लाइक) को आकार (कुल चरणों की संख्या) के संदर्भ में सिम्युलेट करने के लिए पर्याप्त शक्तिशाली है, तो वह स्पेस (मेमोरी) के मामले में भी कुशल होगी।

पेपर सिद्ध करता है कि यह सच नहीं है। लेखकों ने $n$ वेरिएबल्स वाली एक विशिष्ट परिवार की पहेलियाँ बनाईं।

जब ट्री-लाइक रेज़ोल्यूशन का उपयोग करके हल किया जाता है, तो इन पहेलियों के लिए बहुत कम मेमोरी (एक स्थिर मात्रा) की आवश्यकता होती है (आप उन्हें एक बहुत छोटे बॉक्स के साथ हल कर सकते हैं)।
हालाँकि, जब नेगेटिव रेज़ोल्यूशन का उपयोग किया जाता है, तो मेमोरी की आवश्यकता बढ़कर लगभग $\frac{n}{\log n}$ हो जाती है।

इसे समझने के लिए: यदि आपके पास 1,000 वेरिएबल्स वाली पहेली है, तो ट्री-लाइक विधि को शायद ऐसे बॉक्स की आवश्यकता होगी जो केवल 5 वस्तुओं को रख सके, जबकि नेगेटिव विधि को सैकड़ों वस्तुओं को रखने वाले बॉक्स की आवश्यकता होगी। यह एक विशाल अंतर है। यह खोजने जैसा है कि जबकि एक हेलीकॉप्टर (नेगेटिव रेज़ोल्यूशन) एक साइकिल (ट्री-लाइक) के समान समय में उतनी ही दूरी तय कर सकता है, हेलीकॉप्टर को एक विशाल ईंधन टैंक की आवश्यकता होती है, जबकि साइकिल को केवल पानी की एक बोतल की आवश्यकता होती है।

लेखकों ने यह भी दिखाया कि इसका उल्टा भी सच है: ऐसी पहेलियाँ हैं जहाँ नेगेटिव रेज़ोल्यूशन स्पेस के मामले में बहुत कुशल है, लेकिन ट्री-लाइक रेज़ोल्यूशन को एक लॉगरिदमिक मात्रा में स्पेस की आवश्यकता होती है, जो पहेली के आकार के साथ धीरे-धीरे बढ़ता है।

यह क्यों मायने रखता है

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

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

तकनीकी सारांश: ट्री-लाइक (Tree-like) और नेगेटिव रेज़ोल्यूशन में ब्लू पेबलिंग कॉस्ट और स्पेस

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

यह शोध पत्र प्रतिबंधित रेज़ोल्यूशन प्रूफ सिस्टम के भीतर असंतोषजनक (unsatisfiable) फॉर्मुलों को खंडित करने के लिए क्लॉज स्पेस कॉम्प्लेक्सिटी (मेमोरी में एक साथ आवश्यक क्लॉज़ों की न्यूनतम संख्या) को चरित्रित करने की चुनौती को संबोधित करता है। विशेष रूप से, यह ट्री-लाइक रेज़ोल्यूशन (Tree-like Resolution) और नेगेटिव रेज़ोल्यूशन (Negative Resolution) पर ध्यान केंद्रित करता है।

जबकि पेबलिंग गेम्स और प्रूफ कॉम्प्लेक्सिटी के बीच का संबंध अच्छी तरह से स्थापित है (जैसे, ब्लैक पेबल गेम सामान्य रेज़ोल्यूशन में स्पेस को चरित्रित करता है, और रिवर्सिबल पेबलिंग ट्री-लाइक रेज़ोल्यूशन में स्पेस का अनुमान लगाती है), मौजूदा चरित्रण या तो अनुमानित थे (लॉगैरिद्मिक कारकों के साथ) या विशिष्ट लिफ्टेड फॉर्मुलों के लिए सटीक सीमाएँ प्रदान करने में विफल रहे। लेखक एक नया मीट्रिक पेश करने का लक्ष्य रखते हैं जो ट्री-लाइक स्पेस के लिए एक सटीक चरित्रण और नेगेटिव रेज़ोल्यूशन के लिए बेहतर सीमाएँ प्रदान करता है।

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

मुख्य पद्धतिगत योगदान रेड-ब्लू पेबलिंग गेम (Red-Blue Pebbling Game) में एक नए लागत माप (cost measure) की परिभाषा और विश्लेषण है, जिसे ब्लू पेबलिंग कॉस्ट ($Blue(G)$) कहा जाता है।

खेल (The Game): रेड-ब्लू गेम एक सिंगल-सिंक (single-sink) निर्देशित अचक्रीय ग्राफ (sDAG) पर खेला जाने वाला दो-खिलाड़ी खेल है जिसमें एक "पेबलर" (Pebbler) और एक "कलरर" (Colorer) शामिल हैं। पेबलर पेबल्स रखता है, और कलरर उन्हें रंग (लाल या नीला) प्रदान करता है। खेल तब समाप्त होता है जब किसी सोर्स (source) पर या ऐसे वर्टेक्स (vertex) पर रेड पेबल रखा जाता है जिसके पूर्ववर्ती (predecessors) सभी ब्लू होते हैं।
नया माप (The New Measure): मानक रेड-ब्लू प्राइस (जो कुल राउंड गिनता है) या रिवर्सिबल प्राइस (जो कुल पेबल्स गिनता है) के विपरीत, ब्लू कॉस्ट केवल खेल समाप्त होने से पहले ब्लू रंग के किए गए पेबल्स की संख्या को गिनता है।
सैद्धांतिक ढांचा (Theoretical Framework): लेखक पदानुक्रम $Black(G) \leq Blue(G) \leq Rev(G)$ स्थापित करते हैं, जहाँ $Black(G) $मानक ब्लैक पेबल प्राइस है और$ Rev(G) $रिवर्सिबल पेबल प्राइस है। वे सिद्ध करते हैं कि बाइनरी ट्री के लिए,$ Black(G) = Blue(G)$ होता है।
प्रूफ से संबंध (Connection to Proofs): पेपर प्रोवर-डिलेयर गेम (Prover-Delayer game) का उपयोग करता है (जो ट्री-लाइक क्लॉज स्पेस को सटीक रूप से चरित्रित करता है) और उन फॉर्मुलों के अंडरलाइंग ग्राफ पर प्रोवर-डिलेयर गेम को ब्लू पेबलिंग गेम से जोड़ने वाली रणनीतियों का निर्माण करता है।
लिफ्टेड फॉर्मुले (Lifted Formulas): विश्लेषण लिफ्टेड पेबलिंग फॉर्मुलों ( $PebG[\lor]$ और $PebG[\oplus]$ ) तक विस्तृत है, जहाँ मूल पेबलिंग विरोधाभास के वेरिएबल्स को OR या XOR गैजेट्स द्वारा प्रतिस्थापित किया जाता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. ट्री-लाइक रेज़ोल्यूशन स्पेस का सटीक चरित्रण

यह पेपर सिद्ध करता है कि किसी भी असंतोषजनक फॉर्मूला $F$ के लिए, ट्री-लाइक क्लॉज स्पेस ( $Tree\text{-}CS(F)$ ), $F$ के किसी भी रिफ्यूटेशन ग्राफ (केवल ट्री ग्राफ तक सीमित नहीं) के न्यूनतम ब्लू पेबलिंग कॉस्ट के समान है:
$Tree\text{-}CS(F \vdash \square) = \min_{\pi: F \vdash \square} Blue(G_\pi)$

महत्व: यह पिछले परिणामों (जैसे, [TW21]) में सुधार करता है जो ट्री-लाइक स्पेस को अनुमानित करने के लिए रिवर्सिबल पेबलिंग नंबर का उपयोग करते थे, जिससे एक लॉगैरिद्मिक गैप उत्पन्न होता था। यह परिणाम ब्लैक पेबल गेम के माध्यम से सामान्य रेज़ोल्यूशन स्पेस के ज्ञात चरित्रण के समानांतर है।

B. लिफ्टेड पेबलिंग फॉर्मुलों के लिए स्पेस बाउंड्स

लेखक दोनों ट्री-लाइक और नेगेटिव रेज़ोल्यूशन में $PebG[\lor]$ और $PebG[\oplus]$ के लिए स्पेस आवश्यकताओं का विश्लेषण करते हैं:

ट्री-लाइक रेज़ोल्यूशन:
- $PebG[\lor]$ के लिए, स्पेस एसिम्प्टोटिक रूप से $\Theta(Blue(G))$ है।
- $PebG[\oplus]$ के लिए, स्पेस $\Theta(Rev(G))$ है (पिछले कार्य के अनुरूप)।
नेगेटिव रेज़ोल्यूशन:
- $PebG[\lor]$ के लिए, स्पेस $Black(G) $और$ Blue(G) $के बीच सीमित है। पेपर$ O(Blue(G))$ का ऊपरी स्तर (upper bound) और $\Omega(Black(G))$ का निचला स्तर (lower bound) प्रदान करता है।
- $PebG[\oplus]$ के लिए, स्पेस $Black(G) $और$ Rev(G)$ के बीच सीमित है।
- निचले स्तरों को नेगेटिव विड्थ (negative width) के विश्लेषण और ब्लैक पेबलिंग नंबर से संबंधित करके प्राप्त किया गया है।

C. रेज़ोल्यूशन प्रतिबंधों के बीच स्पेस सेपरेशन (Space Separations)

पेपर स्पेस कॉम्प्लेक्सिटी के संबंध में ट्री-लाइक और नेगेटिव रेज़ोल्यूशन के बीच लगभग इष्टतम सेपरेशन स्थापित करता है:

नेगेटिव बनाम ट्री-लाइक (छोटा अंतर): ऐसे फॉर्मूले मौजूद हैं जिन्हें नेगेटिव रेज़ोल्यूशन में कॉन्स्टेंट स्पेस के साथ खंडित किया जा सकता है लेकिन ट्री-लाइक रेज़ोल्यूशन में $\Theta(\log n)$ स्पेस की आवश्यकता होती है।
ट्री-लाइक बनाम नेगेटिव (बड़ा अंतर): $n$ $n$ वेरिएबल्स वाले फॉर्मूलों के परिवार मौजूद हैं जिनमें ट्री-लाइक रेज़ोल्यूशन में कॉन्स्टेंट स्पेस रिफ्यूटेशन होते हैं, लेकिन नेगेटिव रेज़ोल्यूशन में $\Omega(\frac{n}{\log n})$ $Ω (\frac{n}{l o g n})$ स्पेस की आवश्यकता होती है।
- संदर्भ: यह महत्वपूर्ण है क्योंकि नेगेटिव रेज़ोल्यूशन को आकार (size) में ट्री-लाइक रेज़ोल्यूशन को पॉलिनोमियली सिम्युलेट करने के लिए जाना जाता है (केवल छोटे ओवरहेड के साथ)। यह परिणाम दर्शाता है कि जबकि आकार सुरक्षित रहता है, स्पेस नाटकीय रूप से बढ़ सकता है, जो दोनों प्रणालियों के बीच संसाधन आवश्यकताओं में एक मौलिक अंतर को उजागर करता है।

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

लेखक दावा करते हैं कि ब्लू पेबलिंग कॉस्ट प्रतिबंधित रेज़ोल्यूशन सिस्टम में क्लॉज स्पेस के विश्लेषण के लिए एक सटीक उपकरण है।

सैद्धांतिक सटीकता: ट्री-लाइक स्पेस का ब्लू पेबलिंग के माध्यम से सटीक चरित्रण पिछले रिवर्सिबल पेबलिंग विश्लेषणों में पाए जाने वाले लॉगैरिद्मिक एप्रोक्सिमेशन गैप को हटा देता है।
नया सेपरेशन: पेपर एक नया सेपरेशन प्रस्तुत करता है जहाँ एक प्रूफ सिस्टम (नेगेटिव रेज़ोल्यूशन), जो दूसरे (ट्री-लाइक) की तुलना में आकार (size) में कुशल है, स्पेस के मामले में काफी कम कुशल है। यह उस अंतर्ज्ञान के विपरीत है कि आकार-दक्षता अक्सर स्पेस-दक्षता के साथ सह-संबंधित होती है।
खुली समस्याएँ (Open Problems): लेखक नोट करते हैं कि नेगेटिव रेज़ोल्यूशन में लिफ्टेड फॉर्मुलों के लिए बाउंड्स करीब तो हैं, लेकिन पूरी तरह से मेल नहीं खाते (उदाहरण के लिए, कुछ ग्राफ परिवारों के लिए $Black(G) $और$ Blue(G)$ के बीच का गैप)। वे यह प्रश्न उठाते हैं कि क्या पेबलिंग गेम मीजर्स का उपयोग करके इन सीमाओं को और अधिक कड़ा किया जा सकता है।

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