Non-Simple T-Prescriptions Yield T-Complexity Gains Infinitely Often

तकनीकी सारांश: गैर-सरल (Non-Simple) T-प्रिस्क्रिप्शन अनंत बार T-जटिलता लाभ प्रदान करते हैं

समस्या विवरण
यह शोध पत्र T-जटिलता (T-complexity) से संबंधित एक विशिष्ट प्रश्न को संबोधित करता है, जो T-कोड के पुनरावर्ती निर्माण पर आधारित परिमित शब्दों (finite words) के लिए एक नियतात्मक जटिलता माप है। T-जटिलता को T-प्रिस्क्रिप्शन द्वारा परिभाषित किया जाता है, जो T-ऑगमेंटेशन चरणों का एक अनुक्रम है। प्रत्येक चरण एक "कॉपी पैटर्न" (एक वर्तमान कोडवर्ड) और एक "कॉपी फैक्टर" $k \ge 1$ का चयन करता है। एक प्रिस्क्रिप्शन $P$ की T-जटिलता सभी चरणों के लिए $\log_2(k_i + 1)$ का योग है।

एक प्रिस्क्रिप्शन सरल (simple) कहलाता है यदि सभी कॉपी फैक्टर्स 1 हों; अन्यथा, यह गैर-सरल (non-simple) है। टिटचेनर एवं अन्य [5] ने पहले ऐसे परिमित उदाहरण प्रदर्शित किए थे जहाँ गैर-सरल प्रिस्क्रिप्शनों ने दिए गए अधिकतम कोडवर्ड लंबाई के लिए किसी भी सरल प्रिस्क्रिप्शन की तुलना में उच्च T-जटिलता प्राप्त की थी। उन्होंने स्पष्ट रूप से पूछा था कि क्या यह घटना कम से कम दो आकार के प्रत्येक निश्चित वर्णमाला (alphabet) के लिए अनंत बार घटित होती है। विशेष रूप से, समस्या यह पूछती है कि क्या ऐसे अनंत लंबाई $N$ मौजूद हैं जहाँ अनियंत्रित सटीक-लंबाई अधिकतम T-जटिलता, $C_T(N)$, सरल सटीक-लंबाई अधिकतम, $C_T^{(1)}(N)$, से अधिक है।

कार्यप्रणाली (Methodology)
लेखक T-ऑगमेंटेशन के संरचनात्मक गुणों और "नो रीसाइक्लिंग" (no recycling) नियम के तहत कॉपी पैटर्न पर लागू होने वाले प्रतिबंधों पर आधारित एक प्रारंभिक प्रमाण रणनीति का उपयोग करते हैं। कार्यप्रणाली इस प्रकार है:

1. परिभाषाएं और सीमाएं: शोध पत्र $L_m$ को ठीक $m$ चरणों (arity $m$) वाले किसी भी सरल प्रिस्क्रिप्शन द्वारा प्राप्त की जा सकने वाली न्यूनतम संभव अधिकतम कोडवर्ड लंबाई के रूप में परिभाषित करता है। यह $d_m = L_m - L_{m-1}$ को परिभाषित करता है, जो एक सरल प्रिस्क्रिप्शन में $m$-वें चरण को जोड़ने की न्यूनतम लंबाई लागत (length cost) का प्रतिनिधित्व करता है।
2. इन्क्रिमेंट्स (Increments) का विश्लेषण: यह तथ्य कि एक वैध T-प्रिस्क्रिप्शन किसी भी कॉपी पैटर्न का पुन: उपयोग नहीं कर सकता (लेम्मा 3), इसका उपयोग करते हुए, लेखक स्थापित करते हैं कि $m$ अरिटी वाले एक सरल प्रिस्क्रिप्शन को $m$ विशिष्ट गैर-रिक्त शब्दों का उपयोग करना चाहिए। एक परिमित वर्णमाला पर शब्दों के घनत्व का विश्लेषण करके, शोध पत्र यह सिद्ध करता है कि इन विशिष्ट शब्दों की औसत लंबाई $m$ के बढ़ने के साथ अनबाउंडेड (unbounded) रूप से बढ़ती है। फलस्वरूप, अनुक्रम $d_m$ अनबाउंडेड है।
3. जंप्स (Jumps) का अस्तित्व: $d_m$ की अनबाउंडेड प्रकृति यह संकेत देती है कि ऐसे अनंत सूचकांक $m$ मौजूद हैं जहाँ इन्क्रिमेंट सख्ती से बढ़ता है, अर्थात, $d_{m+1} > d_m$।
4. काउंटर-उदाहरणों का निर्माण: किसी भी ऐसे सूचकांक $m$ पर जहाँ $d_{m+1} > d_m$ है, लेखक एक विशिष्ट गैर-सरल प्रिस्क्रिप्शन $\hat{P}_m$ का निर्माण करते हैं। यह अंतिम चरण के कॉपी फैक्टर को 1 से बदलकर 2 करके किया जाता है।
   • $\hat{P}_m$ की नई अधिकतम लंबाई $N_m = L_m + |p_m|$ है, जहाँ $|p_m|$ अंतिम पैटर्न की लंबाई है।
   • क्योंकि $|p_m| \le d_m$ और $d_{m+1} > d_m$, नई लंबाई $N_m$ संतुष्ट करती है $N_m < L_{m+1}$।
   • यह सुनिश्चित करता है कि $N_m$ या उससे कम लंबाई के लिए कोई भी सरल प्रिस्क्रिप्शन $m+1$ या अधिक अरिटी वाला नहीं हो सकता, जिससे $m$ चरणों वाला सर्वोत्तम सरल प्रिस्क्रिप्शन अधिकतम $m$ की जटिलता प्राप्त करेगा।
   • निर्मित गैर-सरल प्रिस्क्रिप्शन $\hat{P}_m$ की जटिलता $(m-1) + \log_2 3$ है, जो $m$ से स्पष्ट रूप से अधिक है।

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

• सकारात्मक उत्तर: शोध पत्र सिद्ध करता है कि प्रत्येक वर्णमाला आकार $r \ge 2$ के लिए, ऐसे अनंत अधिकतम कोडवर्ड लंबाई $N$ मौजूद हैं जहाँ $C_T(N) > C_T^{(1)}(N)$।
• मजबूत अपर-एनवेलप स्टेटमेंट: परिणाम को सरल अपर-एनवेलप $C_T^{(1), \le}(N)$ (लंबाई $\le N$ वाले किसी भी सरल प्रिस्क्रिप्शन की अधिकतम जटिलता) के विरुद्ध सिद्ध किया गया है, जो सटीक-लंबाई मामले के लिए सख्त असमानता को दर्शाता है।
• तंत्र की पहचान: शोध पत्र इन लाभों को संचालित करने वाले तंत्र की पहचान करता है: "नो रीसाइक्लिंग" प्रतिबंध सरल प्रिस्क्रिप्शनों को तेजी से बढ़ते हुए विशिष्ट शब्दों का उपयोग करने के लिए मजबूर करता है, जिससे न्यूनतम लंबाई थ्रेशोल्ड में सख्त ऊपर की ओर जंप (upward jumps) उत्पन्न होते हैं। गैर-सरल प्रिस्क्रिप्शन अगले सरल थ्रेशोल्ड को पार किए बिना, अंतिम चरण के कॉपी फैक्टर को बढ़ाकर $\log_2 3 - 1$ का जटिलता लाभ प्राप्त करके इन अंतरालों का लाभ उठाते हैं।
• प्रारंभिक प्रकृति: प्रमाण को प्रारंभिक (elementary) बताया गया है, जो जटिल एसिम्प्टोटिक विश्लेषण के बजाय गिनती के तर्क (counting arguments) और T-कोड की पुनरावर्ती परिभाषा पर निर्भर करता है।

महत्व और सीमाएं
शोध पत्र दावा करता है कि इसका महत्व टिटचेनर एवं अन्य [5] द्वारा छोड़े गए एक परिमित-लंबाई वाले प्रश्न का एक निश्चित, प्रारंभिक उत्तर प्रदान करने में है। यह प्रदर्शित करता है कि गैर-सरल प्रिस्क्रिप्शनों का लाभ केवल एक अलग लघु-लंबाई घटना नहीं है बल्कि यह अनंत बार घटित होता है।

लेखक कम्प्यूटेशनल दक्षता और संरचना के संबंध में परिणाम की विनम्रता को स्पष्ट रूप से नोट करते हैं:

• प्रमाण जंप सूचकांकों को पहचानने के लिए एक ब्रूट-फोर्स विस्तृत सूची (exhaustive enumeration) पर निर्भर करता है; इन लंबाइयों के लिए कोई क्लोज्ड-फॉर्म अनुक्रम या उन्हें खोजने के लिए कोई कुशल एल्गोरिदम प्रदान नहीं किया गया है।
• निर्मित गैर-सरल प्रिस्क्रिप्शन असमानता के वैध साक्षी (witnesses) हैं, लेकिन उन्हें उन लंबाइयों के लिए अनियंत्रित मैक्सिमाइज़र (maximizers) के रूप में दावा नहीं किया गया है (हालांकि सख्त असमानता बनी रहती है क्योंकि अनियंत्रित अधिकतम सभी वैध प्रिस्क्रिप्शनों पर हावी होता है)।
• शोध पत्र इन अपवाद स्वरूप लंबाइयों के घनत्व, सबसे बड़े संभावित लाभ के परिमाण, या एसिम्प्टोटिक वितरण गुणों को संबोधित नहीं करता है, बल्कि केवल ऐसे अनंत उदाहरणों के अस्तित्व पर ध्यान केंद्रित करता है।