एल्गोरिद्म रिसर्च में नई दिशा: साबित हुआ कि "थोड़ी-सी मेमोरी बहुत अधिक समय से अधिक शक्तिशाली हो सकती है"

• MIT के थिओरेटिकल कंप्यूटर साइंटिस्ट Ryan Williams द्वारा पेश किए गए नए प्रमाण से पता चलता है कि मेमोरी संसाधन समय की तुलना में अधिक शक्तिशाली computational resource हो सकता है
• इसने time-space complexity संबंध पर 50 साल से चली आ रही ठहराव को तोड़ा और सभी एल्गोरिद्म को कम मेमोरी में बदलने का एक तरीका पेश किया
• प्रमाण का मूल विचार space-saving simulation का सामान्यीकरण है, जिससे एल्गोरिद्म की space usage को समय के वर्गमूल स्तर तक घटाया जा सकता है
• इससे PSPACE और P class के अंतर को मात्रात्मक रूप से साबित करने की दिशा में प्रगति हुई है, और आगे इससे भी बड़े अंतर के प्रमाण की संभावना खुली है
• विशेषज्ञ इस उपलब्धि को “हैरान कर देने वाली प्रगति और नई खोज की शुरुआत” मान रहे हैं, और भविष्य में यह परिणाम थिओरेटिकल कंप्यूटर साइंस की अन्य कठिन समस्याओं को सुलझाने का सुराग बन सकता है

---

One Small Step for Space, One Giant Leap for Complexity

Ryan Williams के नए प्रमाण का सार

• 2024 की गर्मियों में MIT के Ryan Williams अपने प्रमाण की समीक्षा करते समय इस निष्कर्ष पर पहुँचे कि जिस विचार को वह गलती समझ रहे थे, वह वास्तव में सही था
• उन्होंने सभी एल्गोरिद्म को कम मेमोरी में चल सकने योग्य रूप में बदलने की एक सामान्य प्रक्रिया प्रस्तावित की
• इसके कारण यह साबित करना संभव हुआ कि कुछ समस्याएँ सीमित समय में हल नहीं की जा सकतीं

समय और स्थान: computation के दो संसाधन

• हर एल्गोरिद्म समय और मेमोरी (space) का उपयोग करता है
• पहले यह माना जाता था कि किसी विशेष समस्या को हल करते समय space, time के अनुपात में होता है
• Williams का प्रमाण गणितीय रूप से स्थापित करता है कि space, time से अधिक शक्तिशाली हो सकता है

थिओरेटिकल कंप्यूटर साइंस की शुरुआत और इतिहास

• Juris Hartmanis और Richard Stearns ने 1960 के दशक में time/space complexity की परिभाषाएँ स्थापित कीं
• उन्होंने समस्याओं को हल करने के लिए जरूरी संसाधनों के आधार पर उन्हें complexity classes में वर्गीकृत करने की नींव रखी
• P वे समस्याएँ हैं जिन्हें उचित समय में हल किया जा सकता है, जबकि PSPACE वे समस्याएँ हैं जिन्हें उपयुक्त मेमोरी के साथ हल किया जा सकता है

पहली प्रगति: 1975 की simulation तकनीक

• Hopcroft, Paul, Valiant ने सभी एल्गोरिद्म को थोड़ी कम space में बदलने की universal simulation procedure विकसित की
• यह time और space के संबंध को स्पष्ट करने की दिशा में पहला कदम था, लेकिन बाद में यह सीमा से टकरा गई
• यह माना गया कि data एक ही space को एक ही समय में साझा नहीं कर सकता, इसलिए आगे प्रगति असंभव है

मोड़ का बिंदु: Squishy Pebbles

• 2010 में अग्रणी complexity theorist Stephen Cook और उनके सहयोगियों ने ट्री इवैल्यूएशन समस्या - Pebbles and Branching Programs for Tree Evaluation नामक एक कार्य तैयार किया और साबित किया कि एक निश्चित सीमा से कम space budget वाले एल्गोरिद्म के लिए यह कार्य असंभव है
  • लेकिन इसमें एक खामी थी। यह प्रमाण उसी सहज मान्यता पर आधारित था जिसे Paul और उनके सहयोगियों ने दशकों पहले अपनाया था
  • यानी, एल्गोरिद्म पहले से भरी हुई space में नया data store नहीं कर सकता
  • 10 साल से अधिक समय तक complexity theorists इस खामी को भरने की कोशिश करते रहे
• Stephen Cook के बेटे James Cook और Ian Mertz ने 2023 में इस पुरानी मान्यता को तोड़ने वाला ट्री इवैल्यूएशन समस्या एल्गोरिद्म प्रकाशित किया Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• उन्होंने एक नया representation model प्रस्तावित किया, जिसमें मेमोरी के भीतर data भौतिक रूप से overlap कर सकता है
• यह तरीका मौजूदा simulation सीमाओं को पार करने की कुंजी बन गया

Williams की निर्णायक छलांग

• छात्रों की प्रस्तुति के बाद Cook-Mertz तकनीक से परिचित हुए Williams को इसे universal simulation पर लागू करने का विचार आया
• नई simulation एल्गोरिद्म की space requirement को time के वर्गमूल स्तर तक घटा सकती है
• उन्होंने फरवरी 2025 में अंतिम पेपर arXiv पर प्रकाशित किया, जिसे अकादमिक जगत से भरपूर प्रशंसा मिली

इस नतीजे का मतलब क्या है

• यह प्रमाण सीधे तौर पर PSPACE > P साबित नहीं करता, लेकिन उस दिशा में आगे बढ़ने के लिए एक निर्णायक ‘गैप’ बनाता है
• अगर भविष्य में इस प्रक्रिया को बार-बार लागू कर और बड़ा अंतर बनाया जा सके, तो P vs PSPACE समस्या के समाधान के करीब पहुँचना संभव हो सकता है
• यह कंप्यूटर साइंस की सबसे पुरानी कठिन समस्याओं में से एक को हल करने की शुरुआत बन सकता है

असर छोड़ने वाला अंत

• Williams ने इस परिणाम पर कहा:
  “मैं वह साबित नहीं कर पाया जिसे मैं सच में साबित करना चाहता था, लेकिन आख़िरकार जो साबित हुआ, वह मेरी चाहत से भी बेहतर निकला।”

[nunojay]

....उम्?

[GN⁺]

Hacker News टिप्पणियाँ

• fuzz को अलग रखें तो, समय t में चलने वाली multi-tape Turing machine को O(sqrt(t log t)) space का उपयोग करके simulate किया जा सकता है, हालांकि आमतौर पर समय t से अधिक लगेगा Simulating Time With Square-Root Space
  • अफसोस यह है कि Quanta के लेख गणित पर लिखते समय बहुत ज़्यादा काव्यात्मक या बढ़ा-चढ़ाकर कहे गए वाक्य इस्तेमाल करते हैं, जिससे गलतफ़हमी पैदा होती है। Quanta लेख में कहा गया कि “कुछ खास कार्यों के लिए उनके रन टाइम के अनुपात में space चाहिए था”, लेकिन केवल complexity hierarchy को देखकर ऐसी कोई सामान्य intuition नहीं निकलती। “कुछ algorithms” की सीमित बात से पूरी intuition नहीं बनाई जा सकती
  • शायद पाठकों के प्रति ज़रूरत से ज़्यादा नरमी है, लेकिन Quanta ने P complexity class को सिर्फ “वे सभी समस्याएँ जिन्हें उचित समय में हल किया जा सकता है” कहकर समझाया और polynomial शब्द का इस्तेमाल ही नहीं किया, यह थोड़ा अपमानजनक लगा
• Perl दर्शन वाली “Camel Book” में ऐसी पंक्ति है: “अगर memory कम है तो खरीद लो, लेकिन अगर समय कम है तो कोई उपाय नहीं”। यह बस एक मज़ेदार किताब है, इसलिए पसंद है
  • मुझे लगता है इस बात का दूसरा पहलू भी है। कोई प्रोग्राम अगर उपलब्ध memory से ज़्यादा माँगता है तो वह अभी चल ही नहीं सकता, जबकि अगर समय ज़्यादा लगे तो कम से कम किसी तरह चल तो सकता है, इसलिए समय भी आखिरकार महत्वपूर्ण resource है
• पहले से गणना किए गए मानों को संग्रहीत करके रखने वाली lookup table की जीत। कभी लगता था कि अगर processor की ज़रूरत ही न पड़े और सभी operations को किसी केंद्रीय जगह पर store किया जा सके, तो processing speed में क्रांतिकारी सुधार हो सकता है, हालांकि असल में fast retrieval अपने आप में एक कठिन समस्या है
  • जब मैंने पहले storage systems में काम शुरू किया था, तब 4KB blocks को पहले से पूरा calculate करके store कर देने का विचार दिया था। फिर किसी ने बताया कि unique 4KB blocks की संख्या ब्रह्मांड के atoms की संख्या से भी अधिक है, और मैं सचमुच हैरान रह गया था
  • HashLife algorithm Conway’s Game of Life में कुछ ऐसा ही काम Turing-complete तरीके से करता है। बहुत जटिल और विविध states होने पर भी भविष्य की states को छलाँग लगाकर पहले से calculate किया जा सकता है, यह बात मुझे हमेशा अद्भुत लगी
  • retrieval lookup को भी cache कर देने के विचार में कोई समस्या नहीं है, ऐसा मज़ाक
  • यह असल में community-level caching, यानी precompiled software distribution के रूप में लागू हो चुका है। पारंपरिक बाधा यह थी कि efficient compilation न कर पाने पर language features छोड़नी पड़ती थीं, लेकिन cloud parallel compilation और global cache से इसे पार किया जा सकता है। रिलीज़ के समय एक बार compile हो जाए, तो सब मिलकर उसका उपयोग कर सकते हैं
  • “अगर सभी operations को केंद्र में store कर दें तो processor की ज़रूरत नहीं रहेगी” वाली बात को आगे बढ़ाते हुए, अब तो search history तक को memoize कर देने की सोच है
• Quanta की शैली इतनी काव्यात्मक है कि यह समझना कठिन है कि यह शोध वास्तव में व्यावहारिक computers पर लागू हो सकता है या सिर्फ़ एक शुद्ध सैद्धांतिक परिदृश्य है। क्या इसका मतलब यह है कि ज़्यादा memory इस्तेमाल करने के बदले computer की गति धीमी हो जाएगी?
• मैं लंबे समय से raster graphics programming कर रहा हूँ, और lookup tables का उपयोग लगभग स्वाभाविक आदत बन चुका है। हाल में मैंने एक server tool बनाया है जिसमें कई shapes को पहले से DB में रख दिया जाता है और query के समय optimized result इस्तेमाल किया जाता है। यह कोई जटिल या रहस्यमय pattern नहीं, बल्कि बहुत सीधा है। किसी MIT professor ने यह अलग से नहीं सिखाया, बस काम करते-करते सीखा, इसलिए इसका गणितीय औचित्य देखकर संतोष हुआ। लगता है algorithms की बहुत-सी practical समझ वास्तव में practitioners के अनुभव से भी आती है (जैसे: winding number algorithm)
  • आजकल game optimization में जो भी प्रगति मिल रही है, वह सब lookup tables को संदर्भ के अनुसार संभालने के तरीकों से जुड़ी है। lookup table का मतलब सिर्फ static array नहीं होना चाहिए; समय के साथ थोड़ा बदलने वाला data भी उतना ही उपयोगी हो सकता है। इससे GPU पर काम करवाने की दिशा में नई समझ मिली। जो tables पहले compile time या runtime पर static रूप से बनती थीं, उनमें से कुछ हिस्से runtime के दौरान बदलकर texture की तरह GPU को भेजना काफ़ी efficient है। lookup table की परिभाषा की सीमा ही धुंधली लगने लगती है
• यह बात सहज लगती है कि space (memory) समय की तुलना में कहीं अधिक संभावित परिणामों को represent कर सकता है। tape length n होने पर O(n) समय तक लिखा जा सकता है, लेकिन अगर वह binary tape है, तो लंबाई n में 2^n configurations हो सकती हैं। सही तरीके से space का उपयोग किया जाए तो समय की तुलना में बहुत अधिक representational power मिलती है
  • मेरी intuition: एक cell में सैकड़ों calculations के intermediate results रखे जा सकते हैं। अगर intermediate results को store ही न कर सकें और हर बार वही चीज़ फिर से calculate करनी पड़े, तो efficiency बहुत गिर जाती है। cache में 0% hit rate वाली स्थिति बहुत दुर्लभ है; ज़्यादातर मामलों में space का उपयोग करके optimization संभव है। इसके उलट, एक unit time से सैकड़ों cells के space को बदल पाना मुश्किल है, और मौजूदा computing architectures में infinite SIMD संभव नहीं है
  • O(1) memory random access की धारणा को बहुत स्वाभाविक मान लिया जाता है, लेकिन वास्तव में computer का आकार बढ़ने पर access cost O(n^(1/3)) तक बढ़ जाती है। data center में यह बात बहुत प्रत्यक्ष रूप से महसूस की जा सकती है। याद पड़ता है कि यह UMA नहीं, कोई दूसरा model था
  • जब तक P ≠ PSPACE सिद्ध नहीं हो जाता, यह ऐसा क्षेत्र है जहाँ intuition से अधिक गणितीय प्रमाण देना कठिन है
  • दूसरी ओर, बात कुछ हद तक सही है, लेकिन जिन समस्याओं को parallelize करना कठिन है, जैसे alternating machine PTIME=PSPACE, उनमें space इतना बड़ा लाभ न दे सके। paper में t/log t से sqrt(t log t) तक की छलाँग क्रांतिकारी है, लेकिन infinite parallelization से भी पार न की जा सकने वाली कुछ वास्तविक सीमाएँ होंगी
  • व्यवहार में यह काम की प्रकृति पर निर्भर करता है। जब storage access assignment operation से बहुत धीमा हो, तब दोबारा calculate करना तेज़ पड़ सकता है
• समय और space के बीच का “tradeoff” इस तरह भी समझा जा सकता है कि जब एक resource को सीमित किया जाता है, तो दूसरे का सर्वोत्तम मान अपने आप नहीं मिल जाता। उदाहरण के लिए sorting algorithms में समय/space/stability तीन constraints हों, तो stability जोड़ने पर समय या space efficiency गिर सकती है। अभी तक ऐसा कोई stable sort नहीं है जो unstable sort जितना तेज़ और उतना ही memory-efficient हो
• मुझे व्यक्तिगत रूप से Quanta Magazine की लेखन शैली पसंद है। यह सिर्फ computer scientists ही नहीं, बल्कि संबंधित क्षेत्रों में रुचि रखने वाले सामान्य पाठकों तक भी दृष्टि का विस्तार करती है। ऊपर से देखने वाला परिप्रेक्ष्य और आत्मीय समझाने का तरीका नए विचार और नए angles देता है
• Ryan Williams के lecture और paper के links साझा किए गए
• अगर single-tape Turing machine input के रूप में binary N ले और tape के दाईं ओर 1 को N बार लिखना चाहे, तो ऐसा लगता है कि समय N में N cells का space चाहिए होगा। फिर यह N से कम space में कैसे simulate हो सकता है? और Turing machine की यह संरचनात्मक विशेषता कि वह tape के किसी भी मनचाहे स्थान पर jump नहीं कर सकती, इसका वास्तविक computers से क्या संबंध है, यह भी जिज्ञासा है
  • multi-tape Turing machines single-tape की तुलना में बहुत तेज़ होती हैं, और यहाँ “space” से मतलब input/output को छोड़कर इस्तेमाल होने वाला temporary workspace है
  • paper का मुख्य फोकस decision problems हैं, यानी केवल 1-bit output वाली स्थितियाँ। अगर output N-bit हो, तो व्याख्या यह है कि वह मूलतः N decision problems को जोड़ने जैसा है