ఒక 1కి 0 కంటే ఎక్కువ ఖర్చైనప్పుడు, కుదింపు కష్టమవుతుంది

ఒక పాఠ్యాన్ని తక్కువ స్థలంలో నిల్వ చేయడానికి లేదా పంపడానికి, ప్రతి చిహ్నానికి (symbol) 0లు, 1లతో చేసిన ఒక పదాన్ని ఇవ్వండి: తరచుగా వచ్చే చిహ్నాలకు పొట్టిది, అరుదైనవాటికి పొడవైనది. ఆ పదాలు ఒక ప్రిఫిక్స్ కోడ్‌ను (prefix code) ఏర్పరచాలి: ఏ పదమూ మరొక పదానికి ప్రారంభం కాకూడదు. {0, 10, 11} పనిచేస్తుంది; {0, 01, 11} పనిచేయదు, ఎందుకంటే 01 అనేది 0తో మొదలవుతుంది. ప్రిఫిక్స్ కోడ్ ఉంటే, బిట్‌ల పొడవైన వరుసను ఎలాంటి విభాజకం (separator) లేకుండానే తిరిగి పదాలుగా విడగొట్టవచ్చు.

అలాంటి కోడ్‌లలో ఉత్తమమైనది — అతి తక్కువ సగటు పొడవు ఉన్నది — 1952లో డి. ఎ. హఫ్‌మన్ (D. A. Huffman) కనుగొన్నారు, వేగంగా పనిచేసే ఒక సరళమైన అత్యాశ (greedy) పద్ధతితో.

అక్షరాలకు ఒక ధర ఉన్నప్పుడు

హఫ్‌మన్ పద్ధతి ఒక 0కి, ఒక 1కి ఒకే ఖర్చు అని ఊహిస్తుంది. అలా కాదనుకుందాం: 1ని ప్రసారం చేయడానికి ఎక్కువ సమయం, లేదా నిల్వ చేయడానికి ఎక్కువ స్థలం పడుతుంది. ఇప్పుడు ప్రతి పదం ఖర్చు దానిలోని అక్షరాల ఖర్చుల మొత్తం, ఒక పదం పొడవు ఎంత ముఖ్యమో దాని కూర్పు కూడా అంతే ముఖ్యం. ఉదాహరణకు ఖర్చులు 1, 3 అయితే, 00, 01 సమాన పొడవు గలవి, కానీ వాటి ఖర్చు 2, 4.

ఈ రూపాంతరానికి (variant) సుదీర్ఘ చరిత్ర ఉంది. ఆర్. ఎం. కార్ప్ (R. M. Karp) 1961లో దీన్ని ఒక పూర్ణాంక ప్రోగ్రామింగ్ (integer programming) సమస్యగా రాశారు. తర్వాతి పరిశోధనలు ఏ స్థిర జత పూర్ణాంక ఖర్చులకైనా ఖచ్చితమైన, సమర్థవంతమైన అల్గోరిథమ్‌లను, కావలసినంత దగ్గరగా ఉత్తమ విలువను (optimum) చేరుకునే ఒక ఉజ్జాయింపు పద్ధతిని (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 ఇన్‌పుట్‌తో పాటు పెరుగుతుంది; ముందే నిర్ణయించిన ఏ ఖర్చుల జతకైనా, ఆ అల్గోరిథమ్‌లు ఇంకా వర్తిస్తాయి.

కోడింగ్ వృక్షంలో దాగిన ఒక చిక్కుప్రశ్న

నిరూపణ తెలిసిన ఒక కష్టమైన సమస్యతో మొదలవుతుంది: ఒక కాగితంపై ఖండనలు (crossings) లేకుండా గీసిన ఒక నెట్‌వర్క్‌లో, ఏ రెండూ ఒకదానితో ఒకటి అనుసంధానం కాని k బిందువులను ఎంచుకోగలమా? తర్వాత అది ఒక కోడింగ్ సమస్యను నిర్మిస్తుంది, దాని అతి చౌకైన కోడ్ ఆ ప్రశ్నకు సమాధానం ఇస్తుంది.

1. ప్రతి ప్రిఫిక్స్ కోడ్ ఒక వృక్షం (tree): 0 ఎడమకు వెళ్తుంది, 1 కుడికి వెళ్తుంది. అక్షరాల ఖర్చులు M, M + 1 అయినప్పుడు, d లోతులో (depth) ఉండి z సంఖ్యలో 1లు ఉన్న ఒక పదం ఖర్చు M × d + z. లోతు ఖర్చులో పెద్ద భాగాన్ని నిర్ణయిస్తుంది, 1ల సంఖ్య చిన్న భాగాన్ని.
2. రచయితలు ఒక కొత్త మధ్యంతర సమస్యను రూపొందించారు: ప్రతి లోతులో వృక్షానికి ఎన్ని ఆకులు (leaves) ఉంటాయో నిర్ణయించి, దాని ఆకులు ఎక్కడ ఉన్నాయో దానికి స్కోరు ఇవ్వడం. ఒక చౌకైన వృక్షం స్థాయి వారీగా పెరిగే కొద్దీ, ఎంచుకున్న బిందువులను ఒక్కొక్కటిగా తనిఖీ చేసే, ప్రతి ఎంపికను నకలు చేసే, ప్రతి లింకును పరీక్షించే ఒక చిన్న ప్రోగ్రామ్‌ను నడపాలి అని వారు చూపిస్తారు. ఏ దగ్గరి దారి (shortcut) అయినా కనీసం ఒక యూనిట్ ఎక్కువ ఖర్చు అవుతుంది; ఎంచుకున్న ప్రతి బిందువు సరిగ్గా ఒక యూనిట్ ఆదా చేస్తుంది.
3. చివరగా, ప్రతి చిహ్నం సరైన లోతుకు వెళ్లక తప్పని విధంగా పౌనఃపున్యాలను (frequencies) సర్దుబాటు చేస్తారు, అప్పుడు స్కోరు కోడింగ్ ఖర్చుకు ఒక స్థిర మొత్తం కలిపినదిగా మారుతుంది.

పత్రంలోని ఒక చిన్న ఉదాహరణ ఖర్చులు ఎంత సూక్ష్మంగా ఉంటాయో చూపిస్తుంది. మూడు చిహ్నాల పౌనఃపున్యాలు 20, 12, 9; అక్షరాల ఖర్చులు 83, 84. (0, 10, 11) కోడ్ ఖర్చు 5,176. (1, 00, 01) కోడ్ ఖర్చు 5,175: ఖరీదైన అక్షరాన్ని అత్యంత తరచుగా వచ్చే చిహ్నానికి ఇవ్వడమే గెలుస్తుంది, ఎందుకంటే అప్పుడు మిగతా రెండు పదాల్లో తక్కువ 1లు ఉంటాయి.

కష్టం ఎక్కడ దాగి ఉంది

రెండవ ఫలితం ఆ ఇబ్బందిని సాధారణ కోడింగ్ లోపలే గుర్తిస్తుంది. హఫ్‌మన్ పద్ధతి అతి తక్కువ సగటు పొడవును వేగంగా కనుగొంటుంది. కానీ ఆ పొడవును చేరుకునే అన్ని కోడ్‌లలో, పౌనఃపున్యంతో భారితం చేసిన (weighted) అతి తక్కువ 1లు ఉన్నదాన్ని ఎంచుకోవడం కూడా NP-సంపూర్ణమే.

ప్రశ్నలు మిగిలే ఉన్నాయి: అన్ని సంఖ్యలూ చిన్నవైనప్పుడు కూడా సమస్య కష్టంగానే ఉంటుందా (దీన్ని బలమైన NP-కఠినత్వం, strong NP-hardness అంటారు), ఒక వేగవంతమైన పద్ధతి ఏ ఖచ్చితత్వానికైనా ఉత్తమ విలువను ఉజ్జాయింపుగా చేరుకోగలదా — ఆ ఖచ్చితత్వంతో పాటు నడుస్తున్న సమయం కూడా సహేతుకంగా పెరిగేలా.

ఒక AIతో కనుగొన్న నిరూపణ

నిరూపణ ఎలా లభించిందో పత్రం స్పష్టంగా చెబుతుంది. రచయితలు మొదట మరింత సాధారణమైన ఒక సమస్యకు కాఠిన్య నిరూపణ (hardness proof) ఇవ్వమని OpenAI యొక్క Codexను అడిగారు, తర్వాత దాన్ని ద్విమానేతర (nonbinary) కోడ్‌లకు, చివరకు ద్విమాన (binary) కోడ్‌లకు విస్తరించమని అడిగారు. Codex రిడక్షన్ (reduction) వ్యూహానికి, దాని గణిత అభివృద్ధికి తోడ్పడింది; ముసాయిదా రాయడంలో, వాదనలను తనిఖీ చేయడంలో, ఉదాహరణలను నిర్మించడంలో కూడా సహాయపడింది. రచయితలు పనికి మార్గనిర్దేశం చేశారు, దిద్దుబాట్లను, సరళీకరణలను కోరారు, వివరణను గణనీయంగా తిరగరాశారు, తుది ప్రకటనలకు, నిరూపణలకు బాధ్యత వహిస్తున్నారు. ఏ ప్రిప్రింట్ లాగే, దీన్ని ఇంకా సహ సమీక్ష (peer review) చేయలేదు.