💻 computer science

On the Complexity of the Skolem Problem at Low Orders

यह शोध पत्र निश्चित क्रम के रैखिक पुनरावृत्ति अनुक्रमों (linear recurrence sequences) पर बाउंडेड स्कोलेम समस्या (bounded Skolem Problem) के लिए एक रैंडमाइज्ड पॉलिनॉमियल-टाइम एल्गोरिदम प्रस्तुत करता है, जो $p$ -adic विश्लेषण का उपयोग करके संभावित शून्य (candidate zeros) को अलग करने और सत्यापन के लिए अरिथमेटिक-सर्किट आइडेंटिटी टेस्टिंग का लाभ उठाकर, क्रम 4 तक की अनरिस्ट्रिक्टेड स्कोलेम समस्या के लिए जटिलता ऊपरी सीमा को $\mathsf{NP}^{\mathsf{RP}}$ से $\mathsf{coRP}$ में सुधारता है।

मूल लेखक: Piotr Bacik, Joël Ouaknine, James Worrell

प्रकाशित 2026-07-21

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

CC BY 4.0

मूल लेखक: Piotr Bacik, Joël Ouaknine, James Worrell

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

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

लेकिन यहाँ एक रहस्य है जिसने दशकों से गणितज्ञों को जगाए रखा है: स्कोलम प्रॉब्लम (The Skolem Problem)। यह एक भ्रामक रूप से सरल प्रश्न पूछता है: "क्या यह नाचता हुआ अनुक्रम कभी शून्य पर पहुँचेगा?" यह सुनने में आसान लगता है, लेकिन क्योंकि ये अनुक्रम अनंत काल तक चल सकते हैं, इसलिए हर एक संख्या को एक-एक करके जाँचना असंभव है। हमें यह भी निश्चित रूप से नहीं पता कि क्या सभी अनुक्रमों के लिए इस प्रश्न का उत्तर देने की कोई सामान्य विधि है। यह एक विशिष्ट, अनंत लंबी धुन के कभी किसी शांत स्वर (silent note) पर पहुँचने की भविष्यवाणी करने जैसा है। इसे हल करना केवल एक गणितीय पहेली नहीं है; यह हमें यह समझने में मदद करता है कि क्या कंप्यूटर प्रोग्राम अंततः चलना बंद कर देंगे (लूप टर्मिनेशन), क्या कुछ रासायनिक प्रतिक्रियाएँ स्थिर होंगी, या क्या एक रोबोट का नियंत्रण तंत्र कभी क्रैश होगा।

अब, एक टीम के शोधकर्ताओं के बारे में सोचिए जिन्होंने इस पहेली के थोड़े अलग संस्करण को सुलझाने का निर्णय लिया। इस मामले में, उन्होंने यह नहीं पूछा कि क्या एक अनुक्रम कभी शून्य पर पहुँचता है, बल्कि उन्होंने पूछा: "क्या यह पहले N चरणों के भीतर शून्य पर पहुँचता है?" वे इसे बाउंडेड स्कोलम प्रॉब्लम (Bounded Skolem Problem) कहते हैं। कल्पना कीजिए कि आपके पास एक खजाने का नक्शा है जो कहता है कि सोना पहले 100 मील के भीतर कहीं दबा है, लेकिन आपको ठीक से नहीं पता कि वह कहाँ है। पुराने नक्शे (पिछला शोध) कम दूरी के लिए सोना खोजने में अच्छे थे, लेकिन जब दूरी बहुत बड़ी हो जाती थी, तो वे बहुत भ्रमित और धीमे हो जाते थे। यह नया शोध उस सोने को खोजने के लिए एक चतुर, उच्च-गति वाली रणनीति प्रस्तुत करता है, भले ही नक्शा कहे कि "पहले एक अरब मील के भीतर देखें।"

"गणितीय जासूस" का जादू

लेखकों, पियोट्र बाचिक, जोएल ओक्वेन और जेम्स वोरेल ने एक रैंडमाइज्ड एल्गोरिदम (randomized algorithm) बनाया है। कंप्यूटर विज्ञान की दुनिया में, "रैंडमाइज्ड" का अर्थ अंधाधुंध अनुमान लगाना नहीं है। यह एक ऐसे जासूस की तरह है जो अगले सुराग का पीछा करने के लिए तय करने हेतु एक भाग्यशाली सिक्के के उछाल का उपयोग करता है, यह जानते हुए कि यह तरीका अविश्वसनीय रूप से तेज़ और लगभग निश्चित रूप से सही है।

यहाँ बताया गया है कि उनका जासूस कैसे काम करता है, एक चंचल उपमा का उपयोग करते हुए:

1. अनंत जंगल और जादुई लेंस
संख्याओं के अनुक्रम की कल्पना एक अनंत जंगल के रूप में करें। हम एक विशिष्ट पेड़ (संख्या शून्य) को खोजना चाहते हैं। जंगल इतना बड़ा है कि हर पेड़ के बीच से गुजरना असंभव है। शोधकर्ता एक विशेष "जादुई लेंस" का उपयोग करते हैं जो p-adic विश्लेषण नामक चीज़ पर आधारित है। आप इस लेंस को एक ऐसे तरीके के रूप में देख सकते हैं जिससे आप जंगल को ज़मीन से नहीं, बल्कि एक अजीब, विकृत आयाम से देखते हैं जहाँ संख्याएँ अलग तरह से व्यवहार करती हैं। इस विकृत दुनिया में, अनुक्रम ऊबड़-खाबड़ चरणों की एक रेखा के बजाय एक चिकनी, बहती हुई नदी (एक गणितीय फलन) बन जाता है।

2. "रेसिड्यू" (Residue) की खोज
हर एक पेड़ की जाँच करने के बजाय, जासूस जंगल को टुकड़ों में देखता है। वे पूछते हैं: "क्या पहले 10 पेड़ों में कोई शून्य है? अगले 10 में क्या है?" वे ऐसा "रेसिड्यू" की जाँच करके करते हैं, जो पेड़ों के पत्तों के रंग की तरह हैं। यदि किसी टुकड़े के पेड़ों का एक विशिष्ट रंग पैटर्न है, तो उसमें एक शून्य हो सकता है। यदि पैटर्न मेल नहीं खाता है, तो जासूस को यकीन हो जाता है कि वहाँ कोई शून्य नहीं है और वह तुरंत उस पूरे टुकड़े को छोड़ देता है। यह "डेप्थ-फर्स्ट सर्च" है जिसका उल्लेख पेपर में किया गया है—यह सर्च ट्री को छाँटने का एक व्यवस्थित तरीका है ताकि आप कभी भी खाली शाखाओं पर समय बर्बाद न करें।

3. "कैंडिडेट" (Candidate) सूची
उनके लेंस के जादू के कारण, जासूस यह सिद्ध कर सकता है कि केवल पॉलीनोमियल रूप से छोटी संख्या में ही ऐसे "कैंडिडेट" पेड़ हैं जो शून्य हो सकते हैं। भले ही जंगल घातीय (exponentially) रूप से विशाल हो (सोचिए अरबों अंकों वाली एक संख्या), जासूस को वास्तव में जाँच करने के लिए संदिग्ध पेड़ों की संख्या आश्चर्यजनक रूप से कम है। यह घास के ढेर में सुई खोजने की खोज को केवल कुछ विशिष्ट स्ट्रॉ (तिनकों) तक सीमित करने जैसा है।

4. अंतिम जाँच
एक बार जब जासूस के पास इस संक्षिप्त कैंडिडेट सूची के पास पहुँच जाता है, तो वह केवल अनुमान नहीं लगाता। वे अरिथमेटिक-सर्किट आइडेंटिटी टेस्टिंग नामक एक शक्तिशाली उपकरण का उपयोग करते हैं। कल्पना कीजिए कि यह एक सुपर-फास्ट कैलकुलेटर है जो यह सत्यापित कर सकता है कि क्या एक जटिल मशीन खराब है (क्या संख्या शून्य है?) पलक झपकते ही। एल्गोरिदम सभी उम्मीदवारों की जाँच करता है। यदि उनमें से एक भी शून्य है, तो उत्तर है "हाँ, अनुक्रम शून्य पर पहुँचता है!" यदि कोई भी शून्य नहीं है, तो उत्तर है "नहीं।"

उन्होंने क्या पाया (और क्या नहीं)

यह पेपर सिद्ध करता है कि किसी भी अनुक्रम के लिए जिसका "ऑर्डर" (वह कितने पिछले नंबरों को देखता है) निश्चित और छोटा है, इस समस्या को पॉलीनोमियल टाइम में हल किया जा सकता है। सरल शब्दोंх में, इसका अर्थ है कि समस्या को हल करने में लगने वाला समय इनपुट के आकार के साथ तर्कसंगly बढ़ता है, न कि अनंत की ओर विस्फोट करता है।

विशेष रूप से, उन्होंने दिखाया कि ऑर्डर 4 (जो पिछले 4 नंबरों को देखता है) वाले अनुक्रमों के लिए, यह समस्या coRP नामक जटिलता वर्ग (complexity class) से संबंधित है। यह एक बड़ी बात है क्योंकि यह पिछले सर्वश्रेष्ठ अनुमान, जो कि NPRP था, की तुलना में एक महत्वपूर्ण सुधार है। इसका अर्थ है कि हम इन विशिष्ट अनुक्रमों के लिए एक निश्चित समाधान के बहुत करीब हैं।

हालाँकि, पेपर बहुत सावधानी से यह भी बताता है कि यह क्या दावा नहीं करता है। यह सभी अनुक्रमों के लिए स्कोलम प्रॉब्लम को हल नहीं करता है, केवल उन अनुक्रमों के लिए जिनका ऑर्डर कम और निश्चित है। यह यह भी दावा नहीं करता कि यह शून्य को एक नियत (deterministic) तरीके से पाता है (बिना भाग्य के 100% निश्चितता); यह एक रैंडमाइज्ड दृष्टिकोण का उपयोग करता है। लेकिन लेखक आश्वस्त हैं कि यह रैंडमाइज्ड विधि अत्यधिक उच्च संभावना के साथ सही है।

वे यह भी बताते हैं कि इस एल्गोरिदम को चलाने में लगने वाला समय अनुक्रम के "ऑर्डर" पर बहुत अधिक निर्भर करता है। यदि ऑर्डर बहुत अधिक हो जाता है, तो एल्गोरिदम घातीय रूप से धीमा हो जाता है। यह उनके तरीके की खामी नहीं है; पेपर सुझाव देता है कि यह धीमापन अपरिहार्य है क्योंकि सामान्य मामले में यह समस्या स्वयं बहुत कठिन (NP-hard) मानी जाती है।

निष्कर्ष

यह पेपर एक असंभव खोज को एक प्रबंधनीय खोज में बदलने का एक उत्कृष्ट उदाहरण है। गहरे गणितीय उपकरणों (p-adic numbers और Mahler series) का उपयोग करके असंभव उम्मीदवारों को बाहर निकालने के माध्यम से, लेखकों ने एक विशाल रेंज के भीतर संख्या अनुक्रम शून्य पर पहुँचता है या नहीं, इसकी जाँच करने का एक तेज़ और विश्वसनीय तरीका बनाया है। जबकि हर संभव अनुक्रम के लिए स्कोलम प्रॉब्लम का अंतिम रहस्य अभी भी अनसुलझा है, यह कार्य अनुक्रमों के एक विशाल और महत्वपूर्ण वर्ग के लिए एक उज्ज्वल मार्ग दिखाता है, यह सिद्ध करता है कि सही गणितीय लेंस के साथ, सबसे अनंत जंगलों का भी अन्वेषण किया जा सकता है।

तकनीकी सारांश: निम्न क्रम (Low Orders) पर स्कोलेम समस्या की जटिलता पर

समस्या की परिभाषा
स्कोलेम समस्या यह पूछती है कि क्या पूर्णांकों पर दी गई एक रैखिक पुनरावृत्ति अनुक्रम (LRS) $\langle u_n \rangle_{n=0}^\infty$ में कोई शून्य पद (अर्थात, क्या ऐसा $n$ मौजूद है कि $u_n = 0$ ) होता है। जबकि सामान्य स्कोलेम समस्या की निर्णयक्षमता (decidability) अभी भी खुली हुई है, यह ज्ञात है कि क्रम 4 या उससे कम के LRS के लिए यह निर्णय योग्य है। यह शोध पत्र बाउंडेड स्कोलेम समस्या (Bounded Skolem Problem) को संबोधित करता है, जहाँ इनपुट में एक LRS और एक सीमा $N$ (बाइनरी में एनकोडेड) शामिल होती है, और कार्य यह निर्धारित करना है कि क्या सीमा $\{0, \dots, N\}$ के भीतर कोई शून्य मौजूद है।

कार्यप्रणाली (Methodology)
लेखक एक रैंडमाइज्ड एल्गोरिदम प्रस्तावित करते हैं जो किसी भी निश्चित क्रम $d$ के LRS के लिए बाउंडेड स्कोलेम समस्या को इनपुट आकार के सापेक्ष बहुपद समय (polynomial time) में हल करता है (हालांकि $d$ के सापेक्ष यह घातीय/exponential है)। यह दृष्टिकोण $p$ -adic विश्लेषण पर आधारित है, जो पूर्णांक अनुक्रम को एक $p$ -adic विश्लेषिक फलन $F: \mathbb{Z}_p \to \mathbb{Z}_p$ में विस्तारित करता है।

मुख्य कार्यप्रणाली घटक निम्नलिखित हैं:

उप-अनुक्रम अपघटन (Subsequence Decomposition): LRS को परिमित संख्या में उप-अनुक्रमों $u_{Mn+\ell}$ में विभाजित किया जाता है जिन्हें $p$ -adic विश्लेषिक फलनों $F_\ell$ द्वारा इंटरपोलेट किया जा सकता है। यह एक अभाज्य संख्या $p$ और एक पूर्णांक $M$ का चयन करके प्राप्त किया जाता है ताकि साथी आव्यूह (companion matrix) $A$ इस प्रकार हो कि $A^M \equiv I \pmod p$ ।
माहलर श्रेणी प्रतिनिधित्व (Mahler Series Representation): $F_\ell$ के पावर सीरीज़ विस्तार के गुणांकों को सीधे गणना करने के बजाय, एल्गोरिदम माहलर श्रेणी विस्तार $F(x) = \sum \beta_k \binom{x}{k}$ का उपयोग करता है। गुणांक $\beta_k$ को डिस्क्रीट डिफरेंस ऑपरेटर $\Delta$ का उपयोग करके सीधे LRS से प्राप्त किया जाता है।
$p$ -adic वैल्युएशन के माध्यम से मूल पृथक्करण (Root Isolation via $p$ -adic Valuation): एल्गोरिदम "उम्मीदवार शून्य" (candidate zeros) की पहचान करने के लिए $p^r \pmod p$ $p^{r} (mod p)$ अवशेष वर्गों (residue classes) पर डेप्थ-फर्स्ट सर्च करता है। यह $F_\ell$ $F_{ℓ}$ के विशिष्ट $p$ $p$ -adic डिस्क $D(z, r)$ $D (z, r)$ के भीतर शून्य की संख्या निर्धारित करने के लिए $p$ -adic वेइरस्ट्रैस प्रिपरेशन प्रमेय (Weierstrass Preparation Theorem) का उपयोग करता है।
- डिस्क के भीतर शून्य की संख्या $j(F)$ द्वारा निर्धारित होती है, जिसे न्यूनतम $p$ -adic वैल्युएशन वाले गुणांक के सबसे बड़े सूचकांक के रूप में परिभाषित किया गया है।
- महत्वपूर्ण रूप से, यह शोध पत्र वैन डेर पोर्टन और श्लिकवेई (Van der Poorten and Schlickewei) के मात्रात्मक परिशोधन का लाभ उठाते हुए यह दर्शाता है कि $j(F_\ell) \le d-1$ है। यह सुनिश्चित करता है कि जांचने के लिए उम्मीदवार शून्यों की संख्या बहुपद रूप से सीमित है, भले ही खोज का स्थान (सीमा $0 $से$ N$) घातीय रूप से बड़ा हो।
सत्यापन (Verification): एक बार जब उम्मीदवार पूर्णांक $n_i$ की पहचान हो जाती है, तो एल्गोरिदम यह जाँचता है कि क्या $u_{n_i} = 0$ है। चूंकि $n_i$ घातीय रूप से बड़ा हो सकता है, इसलिए प्रत्यक्ष गणना अव्यवहार्य है। इसके बजाय, एल्गोरिदम उम्मीदवार पदों के गुणनफल को दर्शाने वाला एक अंकगणितीय सर्किट (arithmetic circuit) बनाता है और शून्य-परीक्षण समस्या को EqSLP (स्ट्रेट-लाइन प्रोग्राम्स की तुल्यता) में बदल देता है, जो एक ज्ञात coRP समस्या है।

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

जटिलता ऊपरी सीमा (Complexity Upper Bound): यह शोध पत्र सिद्ध करता है कि प्रत्येक निश्चित $d \in \mathbb{N}$ के लिए, क्रम $d$ या उससे कम के LRS के लिए बाउंडेड स्कोलेम समस्या coRP में आती है।
क्रम 4 के लिए सुधार: एक प्रत्यक्ष परिणाम के रूप में, क्रम 4 या उससे कम के LRS के लिए (अप्रतिबंधित) स्कोलेम समस्या को coRP में दिखाया गया है। यह पूर्व कार्य [10] द्वारा स्थापित NPRP के सर्वोत्तम ज्ञात ऊपरी स्तर में सुधार करता है।
फंक्शन समस्या: लेखक अपने परिणाम को फंक्शन समस्या संस्करण (सभी शून्य खोजना) तक विस्तारित करते हैं, यह दिखाते हुए कि यह FPEqSLP (coRP के अनुरूप फंक्शन क्लास) में आता है।
सामान्यीकरण (Generalization): परिणामों को MSTV क्लास के LRS (आर्किमिडीयन मानों के तहत अधिकतम 3 प्रभावी मूल या गैर-आर्किमिडीयन के तहत 2 वाले अनुक्रम) और उन LRS तक विस्तारित किया गया है जिनके विशेषता मूल (characteristic roots) परिमेय संख्याओं के मूल हैं, बशर्ते कि क्रम निश्चित हो।

महत्व और दावे
शोध पत्र का दावा है कि रनिंग टाइम में क्रम $d$ पर घातीय निर्भरता संभवतः आवश्यक है, क्योंकि जब $d$ निश्चित नहीं होता है तो बाउंडेड स्कोलेम समस्या NP-hard होती है। हालांकि, निश्चित क्रमों के लिए, एल्गोरिदम $p$ -adic तकनीकों का उपयोग करके एक बहुपद संख्या में उम्मीदवारों को अलग करके विशाल घातीय खोज सीमा को सफलतापूर्वक नेविगेट करता है।

लेखक इस बात पर जोर देते हैं कि हालांकि सैद्धांतिक आधार $p$ -adic विश्लेषण पर निर्भर है, लेकिन उनका कार्यान्वयन पूरी तरह से अंतर्निहित पूर्णांक LRS और अंकगणितीय सर्किटों पर संचालित होता है, जो सीधे $p$ -adic संख्याओं के साथ गणना करने से बचता है। यह कार्य निश्चित-क्रम अनुक्रमों के बाउंडेड इंस्टेंस के लिए एक रैंडमाइज्ड बहुपद-समय प्रक्रिया स्थापित करके, सामान्य स्कोलेम समस्या की निर्णयक्षमता की ओर एक महत्वपूर्ण कदम प्रदान करता है, जो प्रभावी रूप से समस्या को अंकगणितीय सर्किट पहचान परीक्षण (arithmetic circuit identity testing) में बदल देता है। शोध पत्र नोट करता है कि सामान्य मामले के लिए निर्णयक्षमता को सिद्ध करने के लिए संभवतः एक गैर-अपभ्रष्ट (non-degenerate) LRS के सबसे बड़े शून्य पर एक प्रभावी ऊपरी सीमा प्रदर्शित करने की आवश्यकता होगी, एक ऐसी सीमा जिसे लेखक अनुक्रम की विवरण लंबाई के रूप में घातीय मानते हैं।

"गणितीय जासूस" का जादू

उन्होंने क्या पाया (और क्या नहीं)

निष्कर्ष

इसी तरह के और पेपर