নিষিদ্ধ তুলনা থাকলেও সাজানো, প্রায় ততটাই দ্রুত
n-টি বস্তুকে দুটি দুটি করে তুলনা করে ক্রমানুসারে সাজাতে প্রায় n log n-টি তুলনা প্রয়োজনীয়ও, যথেষ্টও। কিন্তু এটি ধরে নেয় যে যেকোনো দুটি বস্তুকে তুলনা করা যায়।
প্রায়ই তা যায় না। লেখকেরা 2011 সালের একটি গবেষণাপত্র থেকে একটি উদাহরণ ধার করেছেন: কয়েকজন প্রার্থী একই চাকরির জন্য আবেদন করেছেন, প্রত্যেকের সঙ্গে আছেন সুপারিশকারীরা (references)। দুজন প্রার্থীকে তুলনা করা যায় কেবল তখনই, যখন কোনো একজন সুপারিশকারী দুজনকেই চেনেন। অনুমোদিত তুলনাগুলো মিলে একটি নেটওয়ার্ক গড়ে, একটি গ্রাফ (graph): প্রতিটি বস্তু একটি বিন্দু, প্রতিটি অনুমোদিত তুলনা একটি সংযোগ। আসল ক্রমটি লুকানো, কিন্তু গ্রাফটিতে তা যে আছে তা নিশ্চিত, একটি পথ হিসেবে, যা প্রতিটি বস্তুকে পরেরটির সঙ্গে যুক্ত করে। প্রশ্ন: ক্রমটি উদ্ধার করতে কয়টি তুলনা লাগে? এটাই সাধারণীকৃত সাজানো (generalized sorting)।
প্রচলিত কৌশল কেন কাজ করে না
ধ্রুপদি অ্যালগরিদমগুলো বেছে নেওয়ার স্বাধীনতার ওপর নির্ভর করে। QuickSort একটি “পিভট” (pivot) বেছে নিয়ে সেটিকে বাকি বেশিরভাগ বস্তুর সঙ্গে তুলনা করে, কিন্তু একটি যথেচ্ছ গ্রাফে এমন কোনো বস্তু না-ও থাকতে পারে, যা বাকি বেশিরভাগের সঙ্গে যুক্ত। MergeSort বস্তুগুলোকে কয়েকটি দলে ভাগ করে প্রতিটি দল সাজায়, কিন্তু একটি দলকে হয়তো একা সাজানোই যায় না: চূড়ান্ত ক্রমে পাশাপাশি থাকা দুটি বস্তু দলের ভেতরে যুক্ত না-ও থাকতে পারে। আরও মৌলিকভাবে, সাধারণ সাজানোয় সবসময় এমন একটি তুলনা হাতে থাকে, যা সম্ভাব্য ক্রমগুলোর একটি ভালো অংশ বাতিল করে দেয়; সীমিত তুলনার ক্ষেত্রে এমন একটিও না থাকতে পারে।
অগ্রগতি ছিল ধীর। 2011 সালে জিয়ি হুয়াং (Zhiyi Huang), সম্পত কান্নান (Sampath Kannan) ও সঞ্জীব খান্না (Sanjeev Khanna) এমন একটি পদ্ধতি খুঁজে পান, যাতে লগারিদমীয় গুণকগুলো বাদ দিলে প্রায় n¹·⁵-টি তুলনা লাগে, আর তখন থেকে যথেচ্ছ গ্রাফের জন্য এই সীমাই টিকে ছিল। তাঁরা এমনকি প্রশ্ন তুলেছিলেন, সমস্যাটি হয়তো সাধারণ সাজানোর চেয়ে মৌলিকভাবে কঠিন, যার জন্য n-কে 1-এর বেশি কোনো ঘাতে তুলতে হবে।
আগে অনুমান, পরে মেরামত
নিউ ইয়র্ক বিশ্ববিদ্যালয়ের সঞ্জীব খান্না, হার্ভার্ড বিশ্ববিদ্যালয়ের অ্যারন পুটারম্যান (Aaron Putterman) এবং নিউ ইয়র্ক বিশ্ববিদ্যালয়েরই জুনকাই সং (Junkai Song) এখন সেই প্রশ্নের উত্তর দিয়েছেন: না। তাঁদের দৈবায়িত (randomised) অ্যালগরিদম যেকোনো গ্রাফে গড়ে প্রায় n log⁴ n-টি তুলনায় সাজিয়ে ফেলে — সাধারণ সাজানোর চেয়ে মাত্র কয়েকটি লগারিদমীয় গুণক বেশি। আর, তাঁরা লিখেছেন, এটি “তুলনামূলকভাবে সরল”। তবে লাভটি তাত্ত্বিক: প্রমাণের ধ্রুবকগুলো বিশাল (2³²-এর মতো গুণক), তাই সুবিধাটি কেবল খুব বড় n-এর ক্ষেত্রেই দেখা যায়।
এটি একটি জানা ফলাফলের ওপর দাঁড়িয়ে আছে: কেউ যদি আপনার হাতে প্রতিটি সংযোগের দিক সম্পর্কে একটি অনুমান তুলে দেয়, যার w-টি ভুল, তাহলে প্রায় n log n + w-টি তুলনায় ক্রমটি উদ্ধার করা যায়। ফলে কাজটি দাঁড়ায় অল্প তুলনা ব্যবহার করে অল্প ভুলের একটি অনুমান তৈরি করা। মূল ধাপগুলো:
- মোটা দাগের একটি প্রথম অনুমান। সংযুক্ত জোড়াগুলোর একটি দৈব নমুনা তুলনা করুন, আর উত্তরগুলোর সঙ্গে সংগতিপূর্ণ যেকোনো একটি ক্রম বেছে নিন। এতে অনেক ভুল থাকে, তবে খুব বেশি নয়।
- ভুলগুলো সারানোর বদলে আলাদা করে রাখা। ভুল অনুমানগুলো সংশোধন না করে অ্যালগরিদমটি গ্রাফের এমন অংশ খুঁজে বের করে, যেখানে ভুল গড়ের চেয়ে ঘন, আর সেগুলো সরিয়ে রাখে। প্রতিটি দফা অবশিষ্ট ভুলগুলোকে, প্রত্যাশিত মানে (in expectation), এক-চতুর্থাংশে নামিয়ে আনে।
- পরে ফিরে আসা। সরিয়ে রাখা সংযোগগুলো সামলানো হয় পরের একটি পর্যায়ে। প্রতিটি পর্যায় তখনো বাকি থাকা সংযোগগুলোর অন্তত অর্ধেকের নিষ্পত্তি করে, তাই এক মিলিয়ন সংযোগের জন্য প্রায় বিশটি পর্যায়ই যথেষ্ট।
যন্ত্রের সাহায্যে পাওয়া একটি প্রমাণ
গবেষণাপত্রের এআই-সংক্রান্ত ঘোষণাটি অস্বাভাবিক রকমের বিস্তারিত। এতে বলা হয়েছে, ChatGPT 6-Astra “উন্নত সীমাগুলো প্রমাণে অপরিহার্য ছিল”। একটি মডেল প্রথমে প্রায় n¹·³³-টি তুলনার একটি অ্যালগরিদম খুঁজে পায়, তারপর আটকে যায়। লেখকেরা সেটিকে n¹·²-এ ঠেলে নেন; তারপর, কয়েক সপ্তাহ ধরে কয়েক ডজন বার নির্দেশনা (prompt) পাওয়ার পর, মডেলগুলো একের পর এক উন্নতি খুঁজে পায় — n^(10/9), n^(17/16), n^(19/18) — শেষে প্রায়-রৈখিক অ্যালগরিদমে পৌঁছানোর আগে। লেখকেরা যোগ করেছেন, তাঁদের নিজেদের মধ্যবর্তী ধাপটি সেই চূড়ান্ত আবিষ্কারের জন্য অপরিহার্য ছিল কি না, তা স্পষ্ট নয়।
যা এখনো খোলা
ফলাফলটি তুলনা গোনে, গণনার সময় নয়: যেভাবে বর্ণিত, অ্যালগরিদমটি বহুপদী সময়ে (polynomial time) চলে না, অথচ 2011-এর পদ্ধতিটি চলত। লেখকেরা তিনটি খোলা প্রশ্নের তালিকা দিয়েছেন: অবশিষ্ট লগারিদমীয় গুণকগুলো সরানো যায় কি না, দৈবতা ছাড়া কোনো অ্যালগরিদম একই রকম ভালো করতে পারে কি না, আর একটি দক্ষ অ্যালগরিদম একই সংখ্যক তুলনায় পৌঁছাতে পারে কি না — কিংবা আদৌ n¹·⁵-কে হারাতে পারে কি না।
