जब 1 की क़ीमत 0 से ज़्यादा हो, तो संपीड़न कठिन हो जाता है

किसी पाठ को संक्षिप्त रूप में सहेजने या भेजने के लिए, हर प्रतीक (symbol) को 0 और 1 से बना एक शब्द दीजिए, बार-बार आने वाले प्रतीकों के लिए छोटा और दुर्लभ प्रतीकों के लिए लंबा। इन शब्दों को एक उपसर्ग कोड (prefix code) बनाना चाहिए: कोई भी शब्द किसी दूसरे शब्द की शुरुआत नहीं हो सकता। {0, 10, 11} चलता है; {0, 01, 11} नहीं, क्योंकि 01 की शुरुआत 0 से होती है। उपसर्ग कोड के साथ, बिटों की एक लंबी शृंखला को बिना किसी विभाजक के वापस शब्दों में काटा जा सकता है।

ऐसा सबसे अच्छा कोड — जिसकी औसत लंबाई सबसे कम हो — 1952 में डी. ए. हफ़मैन (D. A. Huffman) ने खोजा, एक सरल लालची (greedy) नुस्ख़े से जो तेज़ी से चलता है।

जब अक्षरों की क़ीमत हो

हफ़मैन का नुस्ख़ा मानता है कि 0 और 1 की क़ीमत बराबर है। मान लीजिए ऐसा नहीं है: 1 को भेजने में अधिक समय लगता है, या सहेजने में अधिक जगह। अब हर शब्द की क़ीमत उसके अक्षरों की क़ीमतों का योग है, और किसी शब्द की बनावट उतनी ही मायने रखती है जितनी उसकी लंबाई। उदाहरण के लिए, क़ीमतें 1 और 3 हों, तो 00 और 01 बराबर लंबे हैं, लेकिन उनकी क़ीमत 2 और 4 है।

इस रूपांतर (variant) का लंबा इतिहास है। आर. एम. कार्प (R. M. Karp) ने 1961 में इसे एक पूर्णांक-प्रोग्रामन (integer-programming) समस्या के रूप में लिखा। बाद के कार्यों ने पूर्णांक क़ीमतों की किसी भी निश्चित जोड़ी के लिए सटीक, कुशल एल्गोरिद्म खोजे, और एक सन्निकटन योजना (approximation scheme) भी, जो इष्टतम के जितना चाहें उतना पास पहुँचती है। लेकिन जब क़ीमतें स्वयं इनपुट का हिस्सा हों, तब किसी को पता नहीं था कि समस्या कितनी कठिन है। 2021 तक भी इसे खुली समस्या के रूप में सूचीबद्ध किया गया था।

उत्तर: NP-पूर्ण

बेंगलुरु के भारतीय विज्ञान संस्थान (Indian Institute of Science) के एल. सुनील चंद्रन (L. Sunil Chandran) और प्रमाण लैब्स (Pramaana Labs) के ऋषिकेश गज्जला (Rishikesh Gajjala) ने अब सिद्ध किया है कि यह तय करना कि अधिकतम K क़ीमत वाला कोई कोड मौजूद है या नहीं, NP-पूर्ण (NP-complete) है — तब भी जब दोनों क़ीमतें क्रमागत पूर्णांक हों, M और M + 1। कंप्यूटर वैज्ञानिक किसी समस्या को NP-पूर्ण तब कहते हैं जब वह क्लासिक समस्याओं के एक पूरे परिवार जितनी कठिन हो: उनमें से किसी एक के लिए कोई तेज़ सामान्य विधि सबके लिए एक विधि दे देगी, और ऐसी कोई विधि ज्ञात नहीं है। इसलिए सबसे सस्ता कोड खोजना NP-कठिन (NP-hard) है।

निश्चित क़ीमतों वाले तेज़ एल्गोरिद्मों से कोई विरोधाभास नहीं है। प्रमाण में, M इनपुट के साथ बढ़ता है; पहले से तय की गई क़ीमतों की किसी भी जोड़ी के लिए, वे एल्गोरिद्म अब भी लागू होते हैं।

कोडिंग ट्री में छिपी एक पहेली

प्रमाण एक ज्ञात कठिन समस्या से शुरू होता है: किसी काग़ज़ पर बिना किसी कटान (crossing) के खींचे गए नेटवर्क में, क्या आप ऐसे k बिंदु चुन सकते हैं जिनमें से कोई भी दो आपस में जुड़े न हों? फिर वह एक ऐसी कोडिंग समस्या बनाता है जिसका सबसे सस्ता कोड इस प्रश्न का उत्तर देता है।

1. हर उपसर्ग कोड एक ट्री (tree) है: 0 बाईं ओर जाता है, 1 दाईं ओर। जब अक्षरों की क़ीमत M और M + 1 हो, तो जिस शब्द की गहराई d हो और जिसमें z बार 1 आए, उसकी क़ीमत M × d + z होती है। गहराई क़ीमत का बड़ा हिस्सा तय करती है, और 1 की संख्या छोटा हिस्सा।
2. लेखकों ने एक नई मध्यवर्ती समस्या रची: तय कर दीजिए कि ट्री की हर गहराई पर कितनी पत्तियाँ (leaves) हों, और अंक दीजिए कि उसकी पत्तियाँ कहाँ स्थित हैं। उन्होंने दिखाया है कि एक सस्ते ट्री को, जैसे-जैसे वह स्तर-दर-स्तर बढ़ता है, एक छोटा प्रोग्राम चलाना पड़ता है, जो चुने गए बिंदुओं को एक-एक करके जाँचता है, हर चुनाव की प्रति बनाता है और हर कड़ी (link) को परखता है। कोई भी छोटा रास्ता (shortcut) कम से कम एक इकाई अधिक क़ीमत लेता है; हर चुना गया बिंदु ठीक एक इकाई बचाता है।
3. अंत में, आवृत्तियों (frequencies) को इस तरह समायोजित किया जाता है कि हर प्रतीक सही गहराई पर जाने को बाध्य हो, और अंक कोडिंग क़ीमत और एक निश्चित राशि का योग बन जाता है।

शोधपत्र का एक छोटा उदाहरण दिखाता है कि ये क़ीमतें कितनी सूक्ष्म हैं। तीन प्रतीकों की आवृत्तियाँ 20, 12 और 9 हैं, और अक्षरों की क़ीमत 83 और 84 है। कोड (0, 10, 11) की क़ीमत 5,176 है। कोड (1, 00, 01) की क़ीमत 5,175 है: महँगा अक्षर सबसे अधिक बार आने वाले प्रतीक को देना बाज़ी मार लेता है, क्योंकि तब बाक़ी दोनों शब्दों में कम 1 आते हैं।

कठिनाई कहाँ छिपी है

एक दूसरा परिणाम इस कठिनाई को साधारण कोडिंग के भीतर ही ढूँढ़ निकालता है। हफ़मैन का नुस्ख़ा सबसे छोटी औसत लंबाई जल्दी खोज लेता है। लेकिन उस लंबाई तक पहुँचने वाले सभी कोडों में से वह कोड चुनना जिसमें आवृत्ति से भारित, सबसे कम 1 हों, वह भी NP-पूर्ण है।

प्रश्न बाक़ी हैं: क्या समस्या तब भी कठिन रहती है जब सभी संख्याएँ छोटी हों (जिसे प्रबल NP-कठिनता, strong NP-hardness, कहते हैं), और क्या कोई तेज़ योजना इष्टतम का किसी भी परिशुद्धता तक सन्निकटन कर सकती है, ऐसे चलने के समय के साथ जो उस परिशुद्धता के साथ भी उचित रूप से ही बढ़े।

एक AI की मदद से मिला प्रमाण

शोधपत्र बताता है कि यह प्रमाण कैसे प्राप्त हुआ। लेखकों ने पहले OpenAI के Codex से एक अधिक सामान्य समस्या की कठिनता का प्रमाण (hardness proof) माँगा, फिर उससे इसे गैर-द्विआधारी (nonbinary) और अंत में द्विआधारी (binary) कोडों तक विस्तारित करने को कहा। Codex ने रिडक्शन (reduction) की रणनीति और उसके गणितीय विकास में योगदान दिया; उसने मसौदा लिखने, तर्कों की जाँच करने और उदाहरण बनाने में भी मदद की। लेखकों ने काम को दिशा दी, सुधार और सरलीकरण माँगे, प्रस्तुति को काफ़ी हद तक दोबारा लिखा, और अंतिम कथनों तथा प्रमाणों की ज़िम्मेदारी उन्होंने अपने ऊपर ली है। किसी भी प्रीप्रिंट की तरह, इसकी अभी सहकर्मी-समीक्षा (peer review) नहीं हुई है।