مرتبسازی با مقایسههای ممنوع، تقریباً به همان سرعت
برای مرتبکردن n شیء با مقایسهٔ دوبهدوی آنها، حدود n log n مقایسه هم لازم است و هم کافی. اما این با فرض آن است که هر دو شیئی را بتوان با هم مقایسه کرد.
اغلب نمیتوان. نویسندگان مثالی را از مقالهای در 2011 وام میگیرند: چند نامزد برای یک شغل درخواست میدهند و هر یک معرفهایی دارند. دو نامزد را تنها وقتی میتوان مقایسه کرد که معرفی هر دو را بشناسد. مقایسههای مجاز یک شبکه میسازند، یک گراف: هر شیء یک نقطه است و هر مقایسهٔ مجاز یک پیوند. ترتیب واقعی پنهان است، اما تضمین شده که گراف آن را در بر دارد، به صورت مسیری که هر شیء را به شیء بعدی پیوند میدهد. پرسش این است: بازیابی این ترتیب چند مقایسه لازم دارد؟ این همان مرتبسازی تعمیمیافته (generalized sorting) است.
چرا ترفندهای معمول کارساز نیستند
الگوریتمهای کلاسیک بر آزادی انتخاب تکیه دارند. QuickSort یک «محور» (pivot) برمیگزیند و آن را با بیشتر شیءهای دیگر مقایسه میکند، اما یک گراف دلخواه ممکن است هیچ شیئی نداشته باشد که با بیشتر شیءهای دیگر پیوند داشته باشد. MergeSort شیءها را به گروههایی تقسیم میکند و هر گروه را مرتب میکند، اما ممکن است یک گروه بهتنهایی مرتبشدنی نباشد: دو شیئی که در ترتیب نهایی همسایهاند لزوماً درون آن گروه به هم پیوند ندارند. از این بنیادیتر، در مرتبسازی معمولی همیشه مقایسهای در دسترس است که بخش قابلتوجهی از ترتیبهای ممکن را کنار بگذارد؛ با مقایسههای محدود، ممکن است هیچکدام در دسترس نباشد.
پیشرفت کند بود. در 2011، ژییی هوانگ (Zhiyi Huang)، سامپات کانان (Sampath Kannan) و سانجیو کانا (Sanjeev Khanna) روشی یافتند که با چشمپوشی از ضریبهای لگاریتمی، حدود n¹·⁵ مقایسه به کار میبرد، و این کران از آن زمان برای گرافهای دلخواه پابرجا ماند. آنها حتی پرسیدند که آیا این مسئله ممکن است بهطور بنیادی دشوارتر از مرتبسازی معمولی باشد و به n با توانی بزرگتر از 1 نیاز داشته باشد.
نخست پیشبینی، سپس ترمیم
سانجیو کانا از دانشگاه نیویورک، آرون پاترمن (Aaron Putterman) از دانشگاه هاروارد و جونکای سونگ (Junkai Song)، او نیز از دانشگاه نیویورک، اکنون به این پرسش پاسخ میدهند: نه. الگوریتم تصادفی آنها روی هر گرافی بهطور میانگین با حدود n log⁴ n مقایسه مرتب میکند — تنها چند ضریب لگاریتمی بالاتر از مرتبسازی معمولی. و به نوشتهٔ خودشان، «نسبتاً ساده» است. با این حال این بهره نظری است: ثابتهای اثبات بسیار بزرگاند (ضریبهایی مانند 2³²)، پس این برتری تنها برای nهای بسیار بزرگ نمایان میشود.
این الگوریتم بر نتیجهای شناختهشده بنا شده است: اگر کسی حدسی از جهت هر پیوند به شما بدهد که در w تا از پیوندها نادرست باشد، میتوان ترتیب را با حدود n log n + w مقایسه بازیابی کرد. پس کار به این بدل میشود که با مقایسههای کم، حدسی با خطاهای کم ساخته شود. گامهای کلیدی:
- یک حدس نخستین و خام. نمونهای تصادفی از جفتهای پیوندخورده را مقایسه کنید و هر ترتیبی را که با پاسخها سازگار است برگزینید. این حدس خطاهای زیادی دارد، اما نه بیش از حد.
- جداکردن خطاها، به جای اصلاح آنها. الگوریتم به جای تصحیح حدسهای نادرست، بخشهایی از گراف را مییابد که خطاها در آنها از میانگین چگالترند و آنها را کنار میگذارد. هر دور، خطاهای باقیمانده را در امید ریاضی به یکچهارم کاهش میدهد.
- بازگشت در مرحلهای بعد. پیوندهای کنارگذاشته در مرحلهای بعدی رسیدگی میشوند. هر مرحله دستکم نیمی از پیوندهای هنوز معلق را حلوفصل میکند، پس برای یک میلیون پیوند حدود بیست مرحله کافی است.
اثباتی که با ماشینها یافته شد
بخش افشای استفاده از هوش مصنوعی در این مقاله بهطرز غیرمعمولی مفصل است. در آن آمده که ChatGPT 6-Astra «در اثبات کرانهای بهبودیافته ضروری بود». یک مدل نخست الگوریتمی با حدود n¹·³³ مقایسه یافت و سپس درجا ماند. نویسندگان آن را به n¹·² رساندند؛ سپس مدلها، با دهها بار درخواست در طول چند هفته، بهبودهایی پیدرپی یافتند — n^(10/9)، n^(17/16)، n^(19/18) — تا به الگوریتم تقریباً خطی رسیدند. نویسندگان میافزایند که روشن نیست گام میانی خودشان برای آن کشف نهایی ضروری بوده باشد.
آنچه هنوز باز است
این نتیجه شمار مقایسهها را میسنجد، نه زمان محاسبه را: الگوریتم، آنگونه که بیان شده، در زمان چندجملهای اجرا نمیشود، حال آنکه روش 2011 چنین بود. نویسندگان سه پرسش باز را برمیشمارند: آیا میتوان ضریبهای لگاریتمی باقیمانده را حذف کرد، آیا الگوریتمی بدون تصادف میتواند به همین خوبی عمل کند، و آیا یک الگوریتم کارآمد میتواند به همین شمار مقایسه برسد — یا حتی اصلاً از n¹·⁵ بهتر عمل کند.
