1-இன் விலை 0-ஐ விட அதிகமானால், சுருக்குதல் கடினமாகிறது

ஓர் உரையைச் சுருக்கமாகச் சேமிக்கவோ அனுப்பவோ, ஒவ்வொரு குறிக்கும் (symbol) 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) கண்டறிந்தன. ஆனால் விலைகளே உள்ளீட்டின் (input) ஒரு பகுதியாக இருக்கும்போது, அந்தச் சிக்கல் எவ்வளவு கடினமானது என்பது யாருக்கும் தெரியவில்லை. 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 புள்ளிகளைத் தேர்ந்தெடுக்க முடியுமா? பிறகு, எந்தக் குறியீட்டுச் சிக்கலின் மிக மலிவான குறியீடு அந்தக் கேள்விக்கு விடையளிக்கிறதோ, அத்தகைய ஒரு குறியீட்டுச் சிக்கலை அது கட்டமைக்கிறது.

1. எந்த முன்னொட்டுக் குறியீடும் ஒரு மரமே: 0 இடப்புறம் செல்கிறது, 1 வலப்புறம் செல்கிறது. எழுத்துகளின் விலைகள் M, M + 1 ஆக இருக்கும்போது, z எண்ணிக்கையிலான 1-களைக் கொண்ட, d ஆழமுள்ள ஒரு சொல்லின் விலை M × d + z. ஆழம் விலையின் பெரும் பகுதியையும், 1-களின் எண்ணிக்கை சிறு பகுதியையும் நிர்ணயிக்கின்றன.
2. ஆசிரியர்கள் ஒரு புதிய இடைநிலைச் சிக்கலை வடிவமைக்கின்றனர்: மரத்தின் ஒவ்வொரு ஆழத்திலும் எத்தனை இலைகள் உள்ளன என்பதை நிர்ணயித்து, அதன் இலைகள் எங்கே அமர்கின்றன என்பதற்கு மதிப்பெண் அளிப்பது. ஒரு மலிவான மரம், நிலை நிலையாக வளரும்போது, தேர்ந்தெடுக்கப்பட்ட புள்ளிகளை ஒவ்வொன்றாகச் சரிபார்த்து, ஒவ்வொரு தேர்வையும் நகலெடுத்து, ஒவ்வோர் இணைப்பையும் சோதிக்கும் ஒரு சிறிய நிரலை இயக்க வேண்டும் என்று அவர்கள் காட்டுகின்றனர். எந்தக் குறுக்குவழியும் குறைந்தது ஓர் அலகு கூடுதல் விலையைக் கொண்டுவருகிறது; தேர்ந்தெடுக்கப்படும் ஒவ்வொரு புள்ளியும் சரியாக ஓர் அலகைச் சேமிக்கிறது.
3. இறுதியாக, ஒவ்வொரு குறியும் சரியான ஆழத்துக்குக் கட்டாயமாகச் செல்லும்படி நிகழ்வெண்கள் (frequencies) சரிசெய்யப்படுகின்றன; மதிப்பெண், குறியீட்டு விலையுடன் ஒரு நிலையான அளவைக் கூட்டியதாகிறது.

விலைகள் எவ்வளவு நுட்பமானவை என்பதை ஆய்வுக்கட்டுரையில் உள்ள ஒரு சிறிய உதாரணம் காட்டுகிறது. மூன்று குறிகளின் நிகழ்வெண்கள் 20, 12, 9; எழுத்துகளின் விலைகள் 83, 84. (0, 10, 11) என்ற குறியீட்டின் விலை 5,176. (1, 00, 01) என்ற குறியீட்டின் விலை 5,175: விலை அதிகமான எழுத்தை மிக அடிக்கடி வரும் குறிக்குக் கொடுப்பதே வெல்கிறது; ஏனெனில் அப்போது மற்ற இரண்டு சொற்களும் குறைவான 1-களைச் சுமக்கின்றன.

சிரமம் எங்கே மறைந்திருக்கிறது

இரண்டாவது முடிவு, சிக்கல் சாதாரணக் குறியீட்டாக்கத்துக்குள்ளேயே இருப்பதைக் காட்டுகிறது. Huffman-இன் செய்முறை மிகக் குறுகிய சராசரி நீளத்தை விரைவாகக் கண்டறிகிறது. ஆனால் அந்த நீளத்தை எட்டும் எல்லாக் குறியீடுகளிலும், நிகழ்வெண்ணால் எடையிடப்பட்ட மிகக் குறைந்த 1-களைக் கொண்டதைத் தேர்ந்தெடுப்பதும் NP-முழுமையானதே.

சில கேள்விகள் எஞ்சியுள்ளன: எல்லா எண்களும் சிறியவையாக இருக்கும்போதும் சிக்கல் கடினமாகவே இருக்கிறதா (வலுவான NP-கடினத்தன்மை, strong NP-hardness எனப்படுவது), மேலும் அந்தத் துல்லியத்துடன் நியாயமான அளவில் மட்டுமே வளரும் இயக்க நேரத்துடன், எந்தத் துல்லியத்துக்கும் உகந்த மதிப்பை அண்ணளவாக்கக்கூடிய ஒரு வேகமான திட்டம் இருக்கிறதா என்பவை.

ஒரு செயற்கை நுண்ணறிவின் உதவியுடன் கண்டறியப்பட்ட நிரூபணம்

இந்த நிரூபணம் எவ்வாறு பெறப்பட்டது என்பதை ஆய்வுக்கட்டுரை குறிப்பிடுகிறது. ஆசிரியர்கள் முதலில் OpenAI-இன் Codex-இடம் மிகவும் பொதுவான ஒரு சிக்கலுக்கான கடினத்தன்மை நிரூபணத்தைக் கேட்டனர்; பிறகு அதை இருமமல்லாத (nonbinary) குறியீடுகளுக்கும், இறுதியாக இரும (binary) குறியீடுகளுக்கும் நீட்டிக்கக் கேட்டனர். குறைப்பின் (reduction) உத்திக்கும் அதன் கணித மேம்பாட்டுக்கும் Codex பங்களித்தது; வரைவு எழுதுதல், வாதங்களைச் சரிபார்த்தல், உதாரணங்களை உருவாக்குதல் ஆகியவற்றிலும் அது உதவியது. ஆசிரியர்கள் பணியை வழிநடத்தினர், திருத்தங்களையும் எளிமைப்படுத்தல்களையும் கோரினர், விளக்கவுரையைப் பெருமளவில் மீண்டும் எழுதினர்; இறுதிக் கூற்றுகளுக்கும் நிரூபணங்களுக்கும் அவர்களே பொறுப்பேற்கின்றனர். எந்த முன்பதிப்பையும் போலவே, இது இன்னும் சக மதிப்பாய்வு செய்யப்படவில்லை.