کمپیوٹنگ تے مصنوعی ذہانتپری پرنٹنظریہپڑھن لئی ۴ منٹ

منع کیتے موازنیاں نال ترتیب، لگ بھگ اونی ای تیز

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 موازنیاں نال لبھی جا سکدی اے۔ ایس لئی کم ایہہ بن جاندا اے کہ تھوڑے موازنیاں نال گھٹ غلطیاں والا اک اندازہ بنایا جاوے۔ اہم قدم:

  • اک موٹا جیہا پہلا اندازہ۔ جُڑیاں جوڑیاں دے اک بے ترتیب نمونے دا موازنہ کرو تے جواباں نال میل کھاندی کوئی وی ترتیب چُن لوو۔ ایہدے وچ بہت غلطیاں ہوندیاں نیں، پر حد توں ودھ نہیں۔
  • غلطیاں نوں ٹھیک کرن دی بجائے وکھ کرو۔ غلط اندازیاں نوں درست کرن دی بجائے، الگورتھم گراف دے اوہ حصے لبھدا اے جتھے غلطیاں اوسط نالوں ودھ سنگھنیاں نیں تے اوہناں نوں اک پاسے رکھ دیندا اے۔ ہر گیڑ باقی غلطیاں نوں، توقع (expectation) وچ، چار گنا گھٹ کر دیندا اے۔
  • بعد وچ مُڑ آؤ۔ اک پاسے رکھیاں کڑیاں اگلے اک مرحلے وچ سنبھالیاں جاندیاں نیں۔ ہر مرحلہ اجے رہندیاں کڑیاں وچوں گھٹ توں گھٹ اَدھیاں دا فیصلہ کر دیندا اے، ایس لئی اک ملین کڑیاں لئی لگ بھگ ویہہ مرحلے کافی نیں۔

مشیناں نال لبھیا اک ثبوت

پیپر وچ AI بارے دسیا گیا بیان عام نالوں کتے ودھ تفصیلی اے۔ ایہدے وچ لکھیا اے کہ ChatGPT 6-Astra «بہتر حداں ثابت کرن وچ لازمی سی»۔ اک ماڈل نے پہلاں لگ بھگ n¹·³³ موازنیاں والا اک الگورتھم لبھیا، فیر اٹک گیا۔ لکھاریاں نے ایہنوں n¹·² تیکر اپڑایا؛ فیر، کئی ہفتیاں وچ درجناں واری ہدایتاں (prompts) دتے جان مگروں، ماڈلاں نے اک توں بعد اک بہتریاں لبھیاں — n^(10/9)، n^(17/16)، n^(19/18) — تے فیر لگ بھگ لکیری (near-linear) الگورتھم تیکر اپڑ گئے۔ لکھاری ایہہ وی آکھدے نیں کہ ایہہ صاف نہیں کہ اوہناں دا اپنا وچکارلا قدم اوس آخری کھوج لئی لازمی سی یا نہیں۔

کیہ اجے کھُلا اے

نتیجہ موازنے گندا اے، حساب دا ویلا نہیں: جیویں بیان کیتا گیا اے، الگورتھم کثیر رقمی ویلے (polynomial time) وچ نہیں چلدا، جدکہ 2011 والا طریقہ چلدا سی۔ لکھاری تِن کھُلے سوال گناؤندے نیں: کیہ باقی رہندے لاگرتھمی جزو مُکائے جا سکدے نیں، کیہ بے ترتیبی توں بغیر کوئی الگورتھم اینا ای چنگا کر سکدا اے، تے کیہ کوئی کارآمد (efficient) الگورتھم موازنیاں دی ایہو گنتی تیکر اپڑ سکدا اے — یا n¹·⁵ نوں ہرا ای سکدا اے۔