যোগফল লক্ষ্যে মেলে এমন সংখ্যা বাছা, প্রায় সেগুলো পড়ার মতোই দ্রুত
এখানে এমন একটি ধাঁধা, যা যে কেউ বলতে পারে। আপনার কাছে পূর্ণসংখ্যার একটি তালিকা আছে — ধরা যাক 3, 9, 14, 20 — আর একটি লক্ষ্য, ধরা যাক 23। আপনি কি এমন কয়েকটি বাছতে পারেন যাদের যোগফল হুবহু লক্ষ্যের সমান? (এখানে, হ্যাঁ: 3 + 20 বা 9 + 14।) এটিই সাবসেট সাম (Subset Sum), কম্পিউটার বিজ্ঞানের সবচেয়ে মৌলিক সমস্যাগুলোর একটি। গবেষণাপত্রটি একে একটি মৌলিক NP-সম্পূর্ণ (NP-complete) সমস্যা হিসেবে বর্ণনা করে — এমন এক সমস্যা-পরিবার, যা নির্ভুলভাবে সমাধান করা কঠিন বলে পরিচিত।
তবে একটি ফাঁক আছে। সংখ্যাগুলো খুব বড় না হলে চতুর অ্যালগরিদমগুলো এমন সময়ে চলে যা তাদের আকারের ওপর নির্ভর করে। ১৯৫৭ সালে বেলম্যানের ধ্রুপদি পদ্ধতিতে সময় লাগে সংখ্যার গণনা n গুণ লক্ষ্য t-এর সমানুপাতিক। তারপর থেকে অ্যালগরিদম ক্রমাগত উন্নত হয়েছে:
- পিসিঙ্গার (১৯৯৯): n × N-এর সমানুপাতিক, যেখানে N সবচেয়ে বড় সংখ্যা;
- ব্রিংম্যান (২০১৭): মোটামুটি n + t;
- কয়েকটি দল (২০২১–২০২৪): মোটামুটি n + N^(5/3), তারপর n + N^(3/2)।
পরম লক্ষ্য ছিল মোটামুটি n + N সময় — ইনপুট পড়ার চেয়ে খুব বেশি নয়। এই ক্ষেত্রের গবেষকেরা একে এই কাজের ধারার “সবচেয়ে গুরুত্বপূর্ণ অমীমাংসিত সমস্যা” বলেছিলেন।
লক্ষ্য থেকে চুল-পরিমাণ দূরে
চীনের ঝেজিয়াং বিশ্ববিদ্যালয়ের লিন চেন, ইউচেন মাও ও গুওচুয়ান ঝাং একটি অ্যালগরিদম দিয়েছেন যা n + N^(1+ε) সময়ে চলে, যেখানে ε আগে থেকে ঠিক করা যেকোনো ছোট ধনাত্মক সংখ্যা হতে পারে — 0.1, 0.01, 0.001। এটি নির্ধারণবাদী, ঋণাত্মক সংখ্যা ও পুনরাবৃত্ত মান গ্রহণ করে, আর একটি গাণিতিক প্রমাণসহ আসে। লেখকেরা এই সময়কে বলেন প্রায়-সর্বোত্তম (near-optimal)।
ফলাফলটি ভেক্টরেও প্রসারিত হয়: এমনভাবে উপাদান বাছা যাতে একাধিক যোগফল একসঙ্গে নিজ নিজ লক্ষ্যে পৌঁছায়, d স্থানাঙ্কের জন্য N^(d+ε) সময়ে। এটি আবার পূর্ণসংখ্যা প্রোগ্রামিং (integer programming) নিয়ে কয়েকটি দলের তোলা একটি প্রশ্নের একাংশের উত্তর দেয় — এমন সমীকরণ-ব্যবস্থার পূর্ণসংখ্যা সমাধান খোঁজা, যাদের চলরাশিগুলো সীমাবদ্ধ। দুটি ফলাফল স্পষ্টভাবে বের করা হয়েছে: সংখ্যার একটি সেটকে দুটি সমান ভাগে ভাগ করা, আর দুটি অভিন্ন যন্ত্রের মধ্যে কাজ যতটা সম্ভব সমানভাবে বণ্টন করা।
সংখ্যাগুলোকে উচ্চতর মাত্রায় তুলে নেওয়া
মূল ধারণাটি জ্যামিতিক। আগেই জানা ছিল যে সংখ্যাগুলো ঘন হলে এবং লক্ষ্যটি সম্ভাব্য যোগফলের পরিসরের বেশ ভেতরে থাকলে সমস্যাটি সহজ। লেখকদের পর্যবেক্ষণ: সংখ্যার একটি বিক্ষিপ্ত সেট উচ্চতর মাত্রা থেকে দেখলে ঘন দেখাতে পারে।
তাঁদের উদাহরণ সেট {11, 12, 22, 24}। 11 ও 22-কে প্রথম অক্ষ বরাবর এক ধাপ ও দুই ধাপ, আর 12 ও 24-কে দ্বিতীয় অক্ষ বরাবর এক ধাপ ও দুই ধাপ হিসেবে লিখুন। তখন সম্ভাব্য যোগফলগুলো একটি ছোট ৪-বাই-৪ বর্গের প্রতিটি বিন্দু ভরে দেয়। কিন্তু সেই বর্গটিকে আবার একটি রেখায় চেপে দিলে — 11x + 12y হিসাব করে — যোগফলগুলো সাতটি আলাদা গুচ্ছ গড়ে, যাদের মাঝে ফাঁক, ০ থেকে ৬৯-এর মধ্যে ছড়ানো। ফাঁকগুলো অভিক্ষেপের (projection) বিভ্রম; দুই মাত্রায় কাঠামোটি সরল।
অ্যালগরিদমটি যোগাত্মক সমাবেশবিদ্যার (additive combinatorics) ফলাফল ব্যবহার করে যেকোনো ইনপুটের জন্য এমন উচ্চ-মাত্রিক স্থানাঙ্ক তৈরি করে। “ভরা” অঞ্চলের ভেতরে উত্তর আসে বিনা খরচে। কেবল প্রান্তের কাছের একটি সরু অঞ্চলে আসল খাটুনি লাগে, যাকে অ্যালগরিদমটি ছোট ছোট সমস্যায় ভেঙে পুনরাবৃত্তিমূলকভাবে (recursively) সমাধান করে। প্রতিটি দফা সেই অঞ্চলকে তীব্রভাবে সংকুচিত করে, আর সব মিলিয়ে কেবল ধ্রুবক সংখ্যক নতুন মাত্রা যোগ হয়।
প্রমাণটি কীভাবে তৈরি হলো
গবেষণাপত্রটি শুরু হয় একটি “AI দায়মুক্তি” দিয়ে। লেখকেরা মূল প্রমাণ-পথটি নিজেরাই নকশা করেছেন, সমস্যাটির ঘন, বহুমাত্রিক সংস্করণ নিয়ে নিজেদের সাম্প্রতিক কাজের ওপর ভিত্তি করে। তারপর তাঁরা এই ধারণাগুলোকে পূর্ণাঙ্গ গাণিতিক প্রমাণে রূপ দিতে GPT Astra Ultra নামের একটি AI মডেল ব্যবহার করেছেন। এটি কয়েকটি লেমায় আটকে গিয়েছিল, যেগুলোর সমাধান হয়েছে লেখকদের ধারণা দিয়ে; একটি প্রকাশ্য গবেষণা-নোটে কথোপকথনগুলো নথিভুক্ত। মৌলিক এলোমেলোকৃত (randomised) অ্যালগরিদমটি তৈরি হয়ে গেলে মডেলটি “লেখকদের কোনো নির্দেশনা ছাড়াই” একে নির্ধারণবাদী, বহুমাত্রিক সংস্করণে প্রসারিত করেছে। মডেলটি গবেষণাপত্রের খসড়াও তৈরি করেছে এবং, লেখকেরা লিখেছেন, Lean 4 প্রুফ অ্যাসিস্ট্যান্টে একটি প্রমাণ দিয়ে এর মূল ফলাফলগুলো যাচাই করেছে। বিষয়বস্তুর পূর্ণ দায় লেখকেরা নেন।
এখনো ঠিক শেষ রেখা নয়
ঘাতটি হুবহু 1 নয়, বরং 1 + ε, আর ε ছোট হলে লুকানো ধ্রুবকগুলো বড় হয়; মাত্রার সংখ্যার ওপর নির্ভরতাও সর্বোত্তম করা হয়নি। লেখকেরা নিজেরাই অ্যালগরিদমটিকে “বেশ জটিল” বলে বর্ণনা করেছেন। গবেষণাপত্রটি তাত্ত্বিক: এতে কোনো বাস্তবায়ন বা বেঞ্চমার্ক নেই।