ممنوعہ موازنوں کے ساتھ ترتیب، تقریباً اتنی ہی تیز
n اشیاء کو دو دو کا موازنہ کر کے ترتیب میں لانے کے لیے تقریباً n log n موازنے ضروری بھی ہیں اور کافی بھی۔ لیکن یہ اس مفروضے پر مبنی ہے کہ کسی بھی دو اشیاء کا موازنہ کیا جا سکتا ہے۔
اکثر ایسا ممکن نہیں ہوتا۔ مصنفین 2011 کے ایک مقالے سے ایک مثال لیتے ہیں: کئی امیدوار ایک ہی ملازمت کے لیے درخواست دیتے ہیں، اور ہر ایک کے کچھ حوالہ دہندگان (references) ہیں۔ دو امیدواروں کا موازنہ صرف اس وقت ہو سکتا ہے جب کوئی حوالہ دہندہ دونوں کو جانتا ہو۔ اجازت یافتہ موازنے ایک جال، یعنی ایک گراف (graph)، بناتے ہیں: ہر شے ایک نقطہ ہے، اور ہر جائز موازنہ ایک ربط۔ اصل ترتیب پوشیدہ ہے، لیکن اس بات کی ضمانت ہے کہ گراف اسے اپنے اندر رکھتا ہے، ایک ایسے راستے کی صورت میں جو ہر شے کو اگلی شے سے جوڑتا ہے۔ سوال یہ ہے: ترتیب کو دوبارہ حاصل کرنے کے لیے کتنے موازنے درکار ہیں؟ یہی عمومی ترتیب (generalized sorting) ہے۔
عام ترکیبیں کیوں ناکام ہوتی ہیں
کلاسیکی الگورتھم انتخاب کی آزادی پر انحصار کرتے ہیں۔ QuickSort ایک “محور” (pivot) چنتا ہے اور اس کا موازنہ زیادہ تر دوسری اشیاء سے کرتا ہے، لیکن کسی من مانے گراف میں ممکن ہے کوئی ایسی شے ہی نہ ہو جو زیادہ تر دوسری اشیاء سے جڑی ہو۔ MergeSort اشیاء کو گروہوں میں بانٹتا ہے اور ہر گروہ کو ترتیب دیتا ہے، لیکن ممکن ہے کوئی گروہ اکیلے ترتیب دیا ہی نہ جا سکے: دو اشیاء جو آخری ترتیب میں پڑوسی ہوں، ضروری نہیں کہ اس گروہ کے اندر آپس میں جڑی ہوں۔ اس سے بھی بنیادی بات یہ ہے کہ عام ترتیب میں ہمیشہ کوئی ایسا موازنہ دستیاب ہوتا ہے جو ممکنہ ترتیبوں کے ایک اچھے خاصے حصے کو خارج کر دے؛ محدود موازنوں کے ساتھ، ممکن ہے ایسا کوئی موازنہ موجود ہی نہ ہو۔
پیش رفت سست رہی۔ 2011 میں، Zhiyi Huang، Sampath Kannan اور Sanjeev Khanna نے ایک ایسا طریقہ ڈھونڈا جو، لوگارتھمی عوامل (logarithmic factors) کو نظر انداز کرتے ہوئے، تقریباً n¹·⁵ موازنے استعمال کرتا ہے، اور تب سے من مانے گرافوں کے لیے یہی حد قائم رہی۔ انہوں نے تو یہ سوال بھی اٹھایا کہ کیا یہ مسئلہ بنیادی طور پر عام ترتیب سے زیادہ مشکل ہو سکتا ہے، یعنی اسے n کی 1 سے بڑی کسی طاقت جتنے موازنوں کی ضرورت ہو۔
پہلے پیش گوئی، بعد میں مرمت
New York University کے Sanjeev Khanna، Harvard University کے Aaron Putterman، اور New York University ہی کے Junkai Song اب اس سوال کا جواب دیتے ہیں: نہیں۔ ان کا تصادفی (randomised) الگورتھم کسی بھی گراف پر اوسطاً تقریباً n log⁴ n موازنوں میں ترتیب مکمل کر لیتا ہے — عام ترتیب سے صرف چند لوگارتھمی عوامل زیادہ۔ اور، ان کے الفاظ میں، یہ “نسبتاً سادہ” ہے۔ تاہم یہ فائدہ نظری ہے: ثبوت کے مستقلات (constants) بہت بڑے ہیں (2³² جیسے عوامل)، اس لیے برتری صرف بہت بڑے n کے لیے ظاہر ہوتی ہے۔
یہ ایک معلوم نتیجے پر استوار ہے: اگر کوئی آپ کو ہر ربط کی سمت کا ایک اندازہ دے دے، جو ان میں سے w روابط پر غلط ہو، تو ترتیب تقریباً n log n + w موازنوں سے دوبارہ حاصل کی جا سکتی ہے۔ چنانچہ کام یہ بن جاتا ہے کہ کم موازنوں سے کم غلطیوں والا اندازہ تیار کیا جائے۔ کلیدی مراحل:
- ایک ابتدائی موٹا اندازہ۔ جڑے ہوئے جوڑوں کے ایک تصادفی نمونے کا موازنہ کیجیے اور کوئی بھی ایسی ترتیب چن لیجیے جو جوابات سے مطابقت رکھتی ہو۔ اس میں بہت سی غلطیاں ہوتی ہیں، مگر حد سے زیادہ نہیں۔
- غلطیوں کو درست کرنے کے بجائے الگ کر دیں۔ غلط اندازوں کو درست کرنے کے بجائے، الگورتھم گراف کے وہ حصے ڈھونڈتا ہے جہاں غلطیاں اوسط سے زیادہ گھنی ہوں، اور انہیں ایک طرف رکھ دیتا ہے۔ ہر دور باقی غلطیوں کو، توقع کے لحاظ سے (in expectation)، چار گنا کم کر دیتا ہے۔
- بعد میں واپس آئیں۔ ایک طرف رکھے گئے روابط کو بعد کے کسی مرحلے میں نمٹایا جاتا ہے۔ ہر مرحلہ ابھی تک زیرِ التوا روابط میں سے کم از کم آدھے طے کر دیتا ہے، اس لیے ایک ملین روابط کے لیے تقریباً بیس مراحل کافی ہیں۔
مشینوں کی مدد سے ملا ثبوت
مقالے میں AI کے استعمال سے متعلق اعلان غیر معمولی طور پر تفصیلی ہے۔ اس کے مطابق ChatGPT 6-Astra “بہتر حدود ثابت کرنے میں ناگزیر تھا”۔ ایک ماڈل نے پہلے ایک ایسا الگورتھم ڈھونڈا جو تقریباً n¹·³³ موازنے استعمال کرتا تھا، پھر وہ آگے نہ بڑھ سکا۔ مصنفین نے اسے n¹·² تک پہنچایا؛ پھر، کئی ہفتوں کے دوران درجنوں بار ہدایات (prompts) دیے جانے پر، ماڈلز نے یکے بعد دیگرے بہتریاں ڈھونڈیں — n^(10/9)، n^(17/16)، n^(19/18) — یہاں تک کہ وہ تقریباً خطی (near-linear) الگورتھم تک پہنچ گئے۔ مصنفین مزید کہتے ہیں کہ یہ واضح نہیں کہ آیا ان کا اپنا درمیانی قدم اس آخری دریافت کے لیے ضروری تھا۔
کیا ابھی حل طلب ہے
یہ نتیجہ موازنے گنتا ہے، حسابی وقت نہیں: اپنی موجودہ صورت میں، یہ الگورتھم کثیر رقمی وقت (polynomial time) میں نہیں چلتا، جبکہ 2011 کا طریقہ چلتا تھا۔ مصنفین تین کھلے سوالات درج کرتے ہیں: کیا باقی لوگارتھمی عوامل ہٹائے جا سکتے ہیں، کیا بے ترتیبی (randomness) کے بغیر کوئی الگورتھم اتنی ہی اچھی کارکردگی دکھا سکتا ہے، اور کیا کوئی مؤثر (efficient) الگورتھم موازنوں کی اسی تعداد تک پہنچ سکتا ہے — یا سرے سے n¹·⁵ سے بہتر بھی کر سکتا ہے۔
