যখন একটি 1-এর দাম একটি 0-এর চেয়ে বেশি, সংকোচন কঠিন হয়ে যায়

একটি লেখাকে কম জায়গায় সংরক্ষণ করতে বা পাঠাতে, প্রতিটি চিহ্নকে (symbol) 0 আর 1 দিয়ে গড়া একটি শব্দ দিন, ঘন ঘন আসা চিহ্নের জন্য ছোট আর বিরলগুলোর জন্য লম্বা। শব্দগুলোকে একটি প্রিফিক্স কোড (prefix code) গঠন করতে হবে: কোনো শব্দ অন্য কোনো শব্দের শুরু হতে পারবে না। {0, 10, 11} চলে; {0, 01, 11} চলে না, কারণ 0 দিয়ে 01 শুরু হয়। প্রিফিক্স কোড থাকলে, বিটের একটি লম্বা সারিকে কোনো বিভাজক ছাড়াই আবার শব্দে কেটে ফেলা যায়।

এমন সেরা কোডটি — যার গড় দৈর্ঘ্য সবচেয়ে ছোট — 1952 সালে খুঁজে পান ডি. এ. হাফম্যান (D. A. Huffman), একটি সরল লোভী (greedy) প্রণালী দিয়ে — যা প্রতিটি ধাপে সবচেয়ে ভালো দেখানো পছন্দটি বেছে নেয় — যা দ্রুত চলে।

যখন অক্ষরের দাম থাকে

হাফম্যানের প্রণালী ধরে নেয় যে একটি 0 আর একটি 1-এর খরচ সমান। ধরুন তা নয়: 1 পাঠাতে বেশি সময় লাগে, বা সংরক্ষণ করতে বেশি জায়গা। এখন প্রতিটি শব্দের খরচ তার অক্ষরগুলোর খরচের যোগফল, আর একটি শব্দের গঠন তার দৈর্ঘ্যের মতোই গুরুত্বপূর্ণ। যেমন, খরচ 1 ও 3 হলে, 00 আর 01 সমান লম্বা, কিন্তু তাদের খরচ 2 ও 4।

এই রূপভেদের একটি দীর্ঘ ইতিহাস আছে। 1961 সালে আর. এম. কার্প (R. M. Karp) এটিকে একটি পূর্ণসংখ্যা-প্রোগ্রামিং (integer-programming) সমস্যা হিসেবে লেখেন — এমন একটি অপ্টিমাইজেশন, যার অজানা রাশিগুলোকে পূর্ণসংখ্যা হতে হবে। পরের কাজগুলো পূর্ণসংখ্যা খরচের যেকোনো নির্দিষ্ট জোড়ার জন্য নির্ভুল, দক্ষ অ্যালগরিদম খুঁজে পেয়েছে, আর একটি আসন্নীকরণ পদ্ধতি (approximation scheme), যা যত ইচ্ছা সর্বোত্তমের কাছাকাছি পৌঁছায়। কিন্তু যখন খরচগুলো নিজেরাই ইনপুটের অংশ, তখন সমস্যাটি কতটা কঠিন তা কেউ জানত না। এমনকি 2021 সালেও এটি অমীমাংসিত বলে তালিকাভুক্ত ছিল।

উত্তর: NP-সম্পূর্ণ

বেঙ্গালুরুর ইন্ডিয়ান ইনস্টিটিউট অব সায়েন্সের এল. সুনীল চন্দ্রন (L. Sunil Chandran) এবং প্রামাণা ল্যাবসের (Pramaana Labs) ঋষিকেশ গজ্জলা (Rishikesh Gajjala) এখন প্রমাণ করেছেন যে খরচ বড়জোর K এমন একটি কোড আছে কি না, তা নির্ধারণ করা NP-সম্পূর্ণ (NP-complete) — এমনকি যখন দুটি খরচ পরপর দুটি পূর্ণসংখ্যা, M ও M + 1। কম্পিউটার বিজ্ঞানীরা একটি সমস্যাকে NP-সম্পূর্ণ বলেন যখন তা ধ্রুপদি সমস্যাগুলোর একটি পুরো পরিবারের সমান কঠিন: একটির জন্য দ্রুত সাধারণ পদ্ধতি পেলে সবগুলোর জন্য পাওয়া যেত, আর কোনোটিই জানা নেই। সবচেয়ে সস্তা কোডটি খুঁজে বের করা, যা সেই হ্যাঁ-না প্রশ্নের উত্তর তৎক্ষণাৎ দিয়ে দেবে, তাই অন্তত ততটাই কঠিন — পরিভাষায় NP-কঠিন (NP-hard)।

নির্দিষ্ট খরচের জন্য দ্রুত অ্যালগরিদমগুলোর সঙ্গে এর কোনো বিরোধ নেই। প্রমাণে M ইনপুটের সঙ্গে বাড়ে; আগে থেকে নির্দিষ্ট যেকোনো খরচ-জোড়ার জন্য সেই অ্যালগরিদমগুলো এখনও খাটে।

একটি কোডিং গাছে লুকানো ধাঁধা

প্রমাণটি শুরু হয় একটি পরিচিত কঠিন সমস্যা থেকে: কাগজের ওপর কোনো ছেদ ছাড়া আঁকা একটি নেটওয়ার্কে, আপনি কি এমন k-টি বিন্দু বাছতে পারেন যাদের কোনো দুটি পরস্পর যুক্ত নয়? তারপর এটি একটি কোডিং সমস্যা গড়ে তোলে, যার সবচেয়ে সস্তা কোড সেই প্রশ্নের উত্তর দেয়।

যেকোনো প্রিফিক্স কোড একটি গাছ: 0 যায় বাঁয়ে, 1 যায় ডানে, আর প্রতিটি শব্দ একটি পাতা (leaf), একটি শাখার প্রান্ত। d গভীরতার — অর্থাৎ d-টি অক্ষরের — একটি শব্দ, যাতে z-টি 1 আছে, তার খরচ M × d + z, যখন অক্ষরগুলোর খরচ M ও M + 1। গভীরতা নির্ধারণ করে খরচের বড় অংশ, আর 1-এর সংখ্যা ছোট অংশ।
লেখকেরা একটি নতুন মধ্যবর্তী সমস্যা নকশা করেছেন: প্রতিটি গভীরতায় গাছের কতগুলো পাতা থাকবে তা নির্দিষ্ট করুন, আর পাতাগুলো কোথায় বসে তার একটি স্কোর দিন। তাঁরা দেখিয়েছেন যে একটি সস্তা গাছকে, স্তরে স্তরে বেড়ে ওঠার সময়, একটি ছোট প্রোগ্রাম চালাতে হয়, যা বাছাই করা বিন্দুগুলোকে একে একে যাচাই করে, প্রতিটি পছন্দ নকল করে এবং প্রতিটি সংযোগ পরীক্ষা করে। সেই প্রোগ্রাম থেকে যেকোনো বিচ্যুতির খরচ অন্তত এক একক বেশি; বাছাই করা প্রতিটি বিন্দু ঠিক এক একক বাঁচায়।
শেষে, পৌনঃপুনিকতাগুলো (frequencies) এমনভাবে সাজানো হয় যাতে প্রতিটি চিহ্ন সঠিক গভীরতায় যেতে বাধ্য হয়, আর স্কোরটি হয়ে দাঁড়ায় কোডিং খরচ যোগ একটি নির্দিষ্ট পরিমাণ।

গবেষণাপত্রের একটি ছোট উদাহরণ দেখায় খরচগুলো কতটা সূক্ষ্ম। তিনটি চিহ্নের পৌনঃপুনিকতা 20, 12 ও 9; 0-এর খরচ 83 আর 1-এর খরচ 84। (0, 10, 11) কোডটির — সবচেয়ে ঘন ঘন আসা চিহ্নের জন্য 0, বাকি দুটির জন্য 10 ও 11 — খরচ 5,176। (1, 00, 01) কোডটির খরচ 5,175: দামি অক্ষরটি সবচেয়ে ঘন ঘন আসা চিহ্নকে দেওয়াই জেতে, কারণ তখন অন্য দুটি শব্দে কম 1 থাকে।

কাঠিন্য কোথায় লুকিয়ে

দ্বিতীয় একটি ফলাফল সমস্যাটিকে খুঁজে পায় সাধারণ কোডিংয়ের ভেতরেই। হাফম্যানের প্রণালী সবচেয়ে ছোট গড় দৈর্ঘ্য দ্রুত খুঁজে দেয়। কিন্তু যত কোড সেই দৈর্ঘ্যে পৌঁছায়, তাদের মধ্যে পৌনঃপুনিকতা দিয়ে ভারিত হিসেবে সবচেয়ে কম 1 থাকা কোডটি বেছে নেওয়াও NP-সম্পূর্ণ।

প্রশ্ন রয়ে গেছে: সব সংখ্যা ছোট হলেও সমস্যাটি কঠিন থাকে কি না (যাকে বলে শক্তিশালী NP-কাঠিন্য, strong NP-hardness), এবং কোনো দ্রুত পদ্ধতি যেকোনো নির্ভুলতায় সর্বোত্তমের কাছাকাছি মান বের করতে পারে কি না, এমন চলন-সময়ে যা সেই নির্ভুলতার সঙ্গেও যুক্তিসংগতভাবে বাড়ে।

একটি এআই-এর সাহায্যে পাওয়া প্রমাণ

গবেষণাপত্রটি জানায় প্রমাণটি কীভাবে পাওয়া গেছে। লেখকেরা প্রথমে OpenAI-এর Codex-এর কাছে আরও সাধারণ একটি সমস্যার কাঠিন্যের প্রমাণ চেয়েছিলেন, তারপর তাকে বলেছিলেন সেটিকে অ-বাইনারি (nonbinary) এবং শেষে বাইনারি কোডে প্রসারিত করতে। Codex রিডাকশনের (reduction) কৌশলে (নেটওয়ার্ক-ধাঁধাকে একটি কোডিং সমস্যায় অনুবাদ) এবং তার গাণিতিক বিকাশে অবদান রেখেছে; খসড়া লেখা, যুক্তি যাচাই ও উদাহরণ তৈরিতেও সাহায্য করেছে। লেখকেরা কাজটিকে পথ দেখিয়েছেন, সংশোধন ও সরলীকরণ চেয়েছেন, উপস্থাপনাটি উল্লেখযোগ্যভাবে নতুন করে লিখেছেন, এবং চূড়ান্ত বিবৃতি ও প্রমাণের দায়িত্ব নিজেরা নিয়েছেন। যেকোনো প্রিপ্রিন্টের মতো, এটি এখনও পিয়ার রিভিউ (peer review) হয়নি।