जेव्हा 1 ची किंमत 0 पेक्षा जास्त असते, तेव्हा संक्षेपण कठीण होते

मजकूर संक्षिप्तपणे साठवण्यासाठी किंवा पाठवण्यासाठी, प्रत्येक चिन्हाला 0 आणि 1 पासून बनलेला एक शब्द द्या — वारंवार येणाऱ्या चिन्हांसाठी छोटा आणि दुर्मीळ चिन्हांसाठी लांब. हे शब्द मिळून एक उपसर्ग संकेत (prefix code) बनला पाहिजे: कोणताही शब्द दुसऱ्या शब्दाची सुरुवात असता कामा नये. {0, 10, 11} चालतो; {0, 01, 11} चालत नाही, कारण 01 ची सुरुवात 0 ने होते. उपसर्ग संकेत असेल तर, बिट्सची लांब माळ कोणत्याही विभाजकाशिवाय पुन्हा शब्दांत तोडता येते.

असा सर्वोत्तम संकेत — ज्याची सरासरी लांबी सर्वांत कमी आहे — 1952 मध्ये D. A. Huffman यांनी शोधला, जलद चालणाऱ्या एका साध्या लोभी (greedy) कृतीद्वारे.

जेव्हा अक्षरांना किंमत असते

Huffman यांची कृती गृहीत धरते की 0 आणि 1 यांची किंमत सारखीच असते. समजा तसे नाही: 1 प्रसारित करायला अधिक वेळ लागतो, किंवा साठवायला अधिक जागा. आता प्रत्येक शब्दाची किंमत त्याच्या अक्षरांच्या किमतींची बेरीज असते, आणि शब्दाची रचना त्याच्या लांबीइतकीच महत्त्वाची ठरते. उदाहरणार्थ, किमती 1 आणि 3 असताना, 00 आणि 01 सारख्याच लांबीचे आहेत, पण त्यांची किंमत 2 आणि 4 आहे.

या प्रकाराला मोठा इतिहास आहे. 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 इनपुटसोबत वाढतो; आधीच ठरवलेल्या किमतींच्या कोणत्याही जोडीसाठी ते अल्गोरिदम अजूनही लागू होतात.

संकेतन-वृक्षात दडलेले कोडे

सिद्धता एका ज्ञात कठीण समस्येपासून सुरू होते: कागदावर कोणत्याही रेषा एकमेकींना न छेदता काढलेल्या नेटवर्कमध्ये, असे k बिंदू निवडता येतील का ज्यांपैकी कोणतेही दोन एकमेकांशी जोडलेले नाहीत? मग ती एक संकेतनाची समस्या तयार करते जिचा सर्वांत स्वस्त संकेत त्या प्रश्नाचे उत्तर देतो.

कोणताही उपसर्ग संकेत म्हणजे एक वृक्ष: 0 डावीकडे जातो, 1 उजवीकडे. अक्षरांच्या किमती M आणि M + 1 असताना, d खोलीवरील, z वेळा 1 असलेल्या शब्दाची किंमत M × d + z असते. खोली किमतीचा मोठा भाग ठरवते, आणि 1 ची संख्या छोटा भाग.
लेखक एक नवी मध्यवर्ती समस्या रचतात: वृक्षाच्या प्रत्येक खोलीवर किती पाने (leaves) आहेत हे निश्चित करा, आणि त्याची पाने कुठे आहेत त्यानुसार गुण द्या. ते दाखवतात की स्वस्त वृक्षाला, तो पातळी-दर-पातळी वाढत असताना, एक छोटा प्रोग्राम चालवावा लागतो जो निवडलेले बिंदू एकेक करून तपासतो, प्रत्येक निवडीची प्रत करतो आणि प्रत्येक जोडणी तपासतो. कोणताही शॉर्टकट किमान एक एकक अधिक महाग पडतो; निवडलेला प्रत्येक बिंदू नेमके एक एकक वाचवतो.
शेवटी, वारंवारता अशा प्रकारे जुळवल्या जातात की प्रत्येक चिन्हाला योग्य खोलीवर जाणे भाग पडते, आणि गुण म्हणजे संकेतनाची किंमत अधिक एक ठरावीक रक्कम ठरते.

शोधनिबंधातील एक छोटे उदाहरण किमती किती सूक्ष्म आहेत ते दाखवते. तीन चिन्हांच्या वारंवारता 20, 12 आणि 9 आहेत, आणि अक्षरांच्या किमती 83 आणि 84. (0, 10, 11) या संकेताची किंमत 5,176 आहे. (1, 00, 01) या संकेताची किंमत 5,175 आहे: महागडे अक्षर सर्वाधिक वारंवार येणाऱ्या चिन्हाला देणे फायद्याचे ठरते, कारण मग इतर दोन शब्दांमध्ये कमी वेळा 1 येतो.

अडचण कुठे दडलेली आहे

दुसरा निकाल ही अडचण सामान्य संकेतनाच्या आतच शोधून काढतो. Huffman यांची कृती सर्वांत कमी सरासरी लांबी जलद शोधते. पण ती लांबी गाठणाऱ्या सर्व संकेतांपैकी, वारंवारतेनुसार भारित, सर्वांत कमी वेळा 1 असलेला संकेत निवडणे हेदेखील NP-पूर्ण आहे.

प्रश्न शिल्लक आहेत: सर्व संख्या छोट्या असतानाही समस्या कठीण राहते का (तथाकथित प्रबळ NP-कठीणता, strong NP-hardness), आणि एखादी जलद योजना इष्टतमाचा कोणत्याही अचूकतेपर्यंत अंदाज देऊ शकते का, ज्याचा चालण्याचा वेळ त्या अचूकतेसोबतही वाजवीपणे वाढतो.

AI च्या मदतीने सापडलेली सिद्धता

शोधनिबंध ती कशी मिळवली हे स्पष्ट सांगतो. लेखकांनी आधी OpenAI च्या Codex कडे एका अधिक सर्वसाधारण समस्येच्या कठीणतेची सिद्धता मागितली, मग ती द्विमानेतर (nonbinary) आणि शेवटी द्विमान (binary) संकेतांपर्यंत विस्तारण्यास सांगितले. Codex ने रिडक्शनच्या (reduction) रणनीतीत आणि तिच्या गणितीय विकासात योगदान दिले; मसुदा लिहिणे, युक्तिवाद तपासणे आणि उदाहरणे तयार करणे यांतही त्याने मदत केली. लेखकांनी कामाला दिशा दिली, दुरुस्त्या आणि सुलभीकरणे मागितली, मांडणी मोठ्या प्रमाणावर पुन्हा लिहिली, आणि अंतिम विधाने व सिद्धता यांची जबाबदारी स्वीकारली आहे. कोणत्याही प्रीप्रिंटप्रमाणे, त्याचे अद्याप समवयस्क-परीक्षण (peer review) झालेले नाही.