40 বছর পর ভাঙল ক্লিক খোঁজার গতিসীমা
n জন মানুষের একটি সামাজিক নেটওয়ার্ক কল্পনা করুন। তাঁদের মধ্যে কি এমন k জনের একটি দল আছে, যাঁরা সবাই একে অপরকে চেনেন? কম্পিউটারবিজ্ঞানীরা এমন দলকে বলেন k-ক্লিক (k-clique), আর একটি খুঁজে বের করা অগণিত প্রয়োগসহ একটি ধ্রুপদি সমস্যা। সরল পদ্ধতিটি k জন মানুষের প্রতিটি সম্ভাব্য দল যাচাই করে, যা মোটামুটি n^k-টি — বড় নেটওয়ার্কের জন্য আশাহীন।
1985-এর একটি কৌশল আর একটি দীর্ঘ চ্যালেঞ্জ
40 বছরেরও বেশি আগে ইয়ারোস্লাভ নেশেত্রিল (Jaroslav Nešetřil) আর স্ভাতোপ্লুক পোলিয়াক (Svatopluk Poljak) একটি শর্টকাট খুঁজে পান। তাঁরা একটি k-ক্লিকের খোঁজকে একটি বড় গ্রাফে একটি ত্রিভুজের খোঁজে পরিণত করেন, যা আবার করা যায় ম্যাট্রিক্স গুণ করে — ম্যাট্রিক্স হলো সংখ্যার বড় বড় সারণি। খরচ নির্ভর করে ম্যাট্রিক্স গুণের সূচক ω-এর ওপর: তাঁদের পদ্ধতিতে লাগে প্রায় n^(ωk/3) ধাপ। ω-এর সঠিক মান কেউ জানে না। এটি অন্তত 2, আর গবেষণাপত্রটি 9/4-এর একটি সাম্প্রতিক ঊর্ধ্বসীমার উল্লেখ করে।
1985 সালের সেই পদ্ধতির সূচক কখনো হারানো যায়নি। 2004 সালে গেরহার্ড ভোগিঙ্গার (Gerhard Woeginger) গবেষকদের চ্যালেঞ্জ জানান কোনো নির্দিষ্ট k-এর জন্য এর চেয়ে ভালো করতে; দুই দশকেরও বেশি সময় পেরিয়ে যায়। এর মধ্যে k-ক্লিক অনুকল্প (k-Clique Hypothesis) — অর্থাৎ n^(ωk/3) মূলত সম্ভাব্য সেরা — হয়ে ওঠে “সূক্ষ্ম-দানা জটিলতা” (fine-grained complexity) ক্ষেত্রের একটি ভিত্তি। গবেষকেরা এটি ব্যবহার করে যুক্তি দিতেন যে আরও বহু সমস্যা, ব্যাকরণ পার্স করা (parsing) থেকে সংকুচিত ডেটা বিশ্লেষণ পর্যন্ত, এর চেয়ে দ্রুত সমাধান করা যায় না।
একটি চলমান লক্ষ্য
এই অনুকল্প খণ্ডন করার একটি বিশেষ অসুবিধা ছিল। এর পূর্বাভাসিত খরচ নির্ভর করে ω-এর ওপর, যা অজানা। ω-এর আজকের সেরা মানের সাপেক্ষে এগিয়ে থাকা একটি অ্যালগরিদম আর অনুকল্পটিকে হারাতে না-ও পারে, যদি পরে কেউ দ্রুততর ম্যাট্রিক্স গুণ খুঁজে পান।
MIT-র ভার্জিনিয়া ভাসিলেভস্কা উইলিয়ামস (Virginia Vassilevska Williams) আর তেল আবিব বিশ্ববিদ্যালয়ের অর জামির (Or Zamir) সমস্যাটিকে পাশ কাটিয়ে যান। তাঁরা প্রমাণ করেন যে যথেষ্ট বড় প্রতিটি k-এর জন্য একটি k-ক্লিক খুঁজে পাওয়া — এমনকি গোনাও — যায় প্রায় n^((ω/3 − c)k) ধাপে, যেখানে c একটি ধনাত্মক ধ্রুবক, যা k বা ω কোনোটির ওপরই নির্ভর করে না। সাশ্রয়টি মাপা হয় ω-এর প্রকৃত মানের সাপেক্ষে, সেটি শেষ পর্যন্ত যা-ই হোক। এটি টিকে থাকে এমনকি ω = 2 হলেও, যা কল্পনাযোগ্য সেরা পরিস্থিতি।
একটি কীলক ভাঁজ করা
পদ্ধতির মূলে আছে নয়টি শীর্ষবিন্দুর (vertex) নকশা। প্রচলিত পদ্ধতি এগুলোকে তিনটি করে তিন দলে ভাগ করে এবং তিনটি বিশাল ম্যাট্রিক্স গুণ করে। লেখকেরা নজর দেন একটি কীলকের (wedge) দিকে — একটি শীর্ষবিন্দু ভাগ করে নেওয়া দুটি বাহু (edge) — এবং দুটি ম্যাট্রিক্সের মাঝখানে এমন একটি সারণি বসান, যা কিছুই বদলায় না: একক ম্যাট্রিক্স (identity)। তারপর তাঁরা সেই একক ম্যাট্রিক্সকে লেখেন কয়েকটি “অদলবদলের” (swaps) যোগফল হিসেবে, যাদের প্রত্যেকটি কীলকের দুটি বাহুকে মিলিয়ে একটিতে পরিণত করে, সঙ্গে থাকে নিম্ন র্যাংকের (low rank) একটি অবশিষ্টাংশ।
অদলবদলগুলো থেকে মেলে কম বাহুবিশিষ্ট সরলতর নকশা, যেগুলো আবার একই পদ্ধতিতে সামলানো হয়; নয়-শীর্ষবিন্দুর একটি নকশায় সর্বোচ্চ 36টি বাহু থাকে, তাই পুনরাবৃত্তি (recursion) একসময় শেষ হয়। নিম্ন-র্যাংকের অবশিষ্টাংশ যে ম্যাট্রিক্সগুলো গুণ করতে হয় সেগুলোকে ছোট করে দেয়। কৌশলটি একসঙ্গে দুটি আলাদা কীলকে প্রয়োগ করার ফলেই ω = 2 হলেও একটি লাভ টিকে থাকে। এরপর নয়ের গুণিতক যেকোনো k-কে নয়টি খণ্ডে ভাগ করা যায়।
বাস্তব, তবে ক্ষুদ্র
লেখকেরা লাভের কোনো সংখ্যা দেননি। তাঁরা ধ্রুবকগুলোকে বর্ণনা করেন “অপ্টিমাইজেশন ছাড়া অতিক্ষুদ্র থেকে উল্লেখযোগ্য অপ্টিমাইজেশনসহ ক্ষুদ্র পর্যন্ত” হিসেবে। মূল কথা ব্যবহারিক গতি নয়: কথা হলো, কয়েক দশক ধরে বিশ্বাস করা একটি বাধার আসলে কোনো অস্তিত্বই নেই।
এর প্রভাব ক্লিক ছাড়িয়েও পৌঁছায়। Max-Cut আর Max-2-SAT-এর মতো কঠিন অপ্টিমাইজেশন সমস্যার নির্ভুল অ্যালগরিদম, যেগুলো n চলরাশির জন্য প্রায় 2^(ωn/3) ধাপে চলত, এখন একটি ছোট সূচকও পায়। একই কথা খাটে যেকোনো নির্দিষ্ট ছোট গ্রাফের প্রতিলিপি গোনার ক্ষেত্রেও।
AI কী করেছে
একটি আলাদা অংশে লেখকেরা বর্ণনা করেন, তাঁরা কীভাবে ChatGPT-6-এর সঙ্গে কাজ করেছেন, যা ব্যবহার করা হয়েছিল এর সর্বজনীন ওয়েব ইন্টারফেসের মাধ্যমে। পাঁচ-জনের ক্লিক নিয়ে তাঁদের নিজেদের ধারণা আর আরেকটি অনুমান — এক্সপোনেনশিয়াল টাইম হাইপোথিসিস (Exponential Time Hypothesis) — খণ্ডনকারী OpenAI-এর একটি সাম্প্রতিক ফল থেকে শুরু করে, মডেলটি 5-ক্লিকের জন্য একটি প্রথম, জটিল উন্নতি খুঁজে পায়। লেখকেরা তারপর AI-এর সাহায্যে সেটিকে ছেঁকে পরিণত করেন প্রমাণের কেন্দ্রে থাকা বীজগাণিতিক বিভাজনে (algebraic decomposition), যাকে তাঁরা মনে করেন “প্রায়-সম্পূর্ণভাবে AI-এর অবদান”। এর চারপাশে গড়া অ্যালগরিদমিক কাঠামোটি, তাঁদের ভাষায়, মূলত তাঁদের নিজেদের।
একটি মন্তব্য আলাদা করে চোখে পড়ে। AI-এর তৈরি দুর্বোধ্য প্রমাণ মানুষের পক্ষে পড়া কঠিন, লেখকেরা উল্লেখ করেন — এবং তাঁরা “মুগ্ধ হয়েছেন যে সেগুলো AI-এর নিজের পক্ষেও বোঝা কঠিন”।
