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

کلیکاں لبھن دی رفتار دی حد 40 ورھیاں مگروں ٹُٹ گئی

n لوکاں والے اک سوشل نیٹ ورک دا تصور کرو۔ کیہ اوہناں وچوں k لوکاں دی کوئی اجیہی ٹولی اے جیہدے سارے جی اک دوجے نوں جاندے ہون؟ کمپیوٹر سائنسدان اجیہی ٹولی نوں k-کلیک (k-clique) آکھدے نیں، تے اک لبھنا اک کلاسیکی مسئلہ اے جیہدے ان گنت استعمال نیں۔ سِدھا سادا طریقہ k لوکاں دی ہر ممکنہ ٹولی جانچدا اے، جو لگ بھگ n^k ہوندیاں نیں — وڈے نیٹ ورکاں لئی ناامیدی والا کم۔

1985 دا اک گُر تے اک لمّا چیلنج

40 توں ودھ ورھے پہلاں، Jaroslav Nešetřil تے Svatopluk Poljak نے اک چھوٹا راہ (shortcut) لبھیا۔ اوہناں نے k-کلیک دی کھوج نوں اک وڈے گراف وچ اک تکون (triangle) دی کھوج وچ بدل دتا، جو اگوں میٹرکساں (matrices) نوں ضرب دے کے کیتی جا سکدی اے، یعنی عدداں دیاں وڈیاں جدولاں۔ لاگت ω اُتے منحصر اے، جو میٹرکس ضرب دا قوت نما (exponent) اے: اوہناں دا طریقہ لگ بھگ n^(ωk/3) قدم لیندا اے۔ کسے نوں ω دی ٹھیک قدر نہیں پتا۔ ایہہ گھٹو گھٹ 2 اے، تے مقالہ 9/4 دی اک حالیہ اُتلی حد (upper bound) دا حوالہ دیندا اے۔

1985 والے اوس طریقے دا قوت نما کدی نہیں ہرایا گیا۔ 2004 وچ، Gerhard Woeginger نے کھوجیاں نوں کسے مقرر k لئی ایس توں بہتر کرن دا چیلنج دتا؛ دو دہاکیاں توں ودھ ویلا لنگھ گیا۔ ایس دوران k-کلیک مفروضہ (k-Clique Hypothesis) — کہ n^(ωk/3) بنیادی طور اُتے سب توں چنگا ممکن اے — «باریک دانے والی پیچیدگی» (fine-grained complexity) دی اک نینہہ بن گیا۔ کھوجیاں نے ایہنوں ایہہ دلیل دین لئی ورتیا کہ بہت سارے ہور مسئلے وی، گرامراں دی پارسنگ (parsing) توں لے کے دبائے ہوئے (compressed) ڈیٹا دے تجزیے تیکر، ایس توں تیز حل نہیں کیتے جا سکدے۔

اک ہلدا ہویا نشانہ

ایس مفروضے نوں رد کرن وچ اک خاص اوکھ سی۔ ایہدی پیشین گوئی والی لاگت ω اُتے منحصر اے، جو نامعلوم اے۔ اک الگورتھم جو ω دی اج دی سب توں چنگی قدر نوں ہراندا اے، مفروضے نوں ہرانا چھڈ سکدا اے جے بعد وچ کوئی میٹرکس ضرب دا تیز طریقہ لبھ لوے۔

MIT توں Virginia Vassilevska Williams تے Tel Aviv University توں Or Zamir نے ایس مسئلے توں بچن دا راہ کڈھ لیا اے۔ اوہناں نے ثابت کیتا اے کہ ہر کافی وڈے k لئی، اک k-کلیک لگ بھگ n^((ω/3 − c)k) قدماں وچ لبھی — تے گنی وی — جا سکدی اے، جتھے c اک مثبت مستقل (constant) اے جو نہ k اُتے منحصر اے نہ ω اُتے۔ بچت ω دی اصل قدر دے مقابلے ناپی جاندی اے، اوہ جو وی نکلے۔ ایہہ اوس حال وچ وی قائم رہندی اے جے ω = 2 ہووے، جو سب توں چنگی سوچی جا سکن والی صورت اے۔

اک ویج نوں تہہ کرنا

طریقے دا دل نو بندواں (vertices) والے نمونیاں (patterns) نال جُڑیا اے۔ معیاری طریقہ اوہناں نوں تن تن دیاں تن ٹولیاں وچ ونڈدا اے تے تن بہت وڈیاں میٹرکساں نوں ضرب دیندا اے۔ لکھاری اک ویج (wedge) نوں ویکھدے نیں — دو لکیراں (edges) جو اک بندو سانجھا کردیاں نیں — تے دو میٹرکساں وچکار اک اجیہی جدول پا دیندے نیں جو کجھ نہیں بدلدی: شناختی میٹرکس (identity)۔ فیر اوہ اوس شناختی میٹرکس نوں کجھ «ادلا بدلیاں» (swaps) دے جوڑ وجوں لکھدے نیں، جیہناں وچوں ہر اک ویج دیاں دوہاں لکیراں نوں رلا کے اک بنا دیندی اے، نالے گھٹ رینک (low rank) والا اک بچیا ہویا حصہ۔

ادلا بدلیاں توں گھٹ لکیراں والے سادے نمونے ملدے نیں، جیہناں نوں فیر اوسے طریقے نال نجٹھیا جاندا اے؛ نو بندواں والے نمونے وچ ودھ توں ودھ 36 لکیراں ہوندیاں نیں، ایس لئی ایہہ دہرائی (recursion) مُک جاندی اے۔ گھٹ رینک والا بچیا ہویا حصہ ضرب دین والیاں میٹرکساں نوں سنگوڑ دیندا اے۔ ایہہ گُر اکو ویلے دو وکھرے ویجاں اُتے لاؤنا ای اوہ گل اے جو ω = 2 ہون تے وی فائدہ قائم رکھدی اے۔ فیر کوئی وی k جو نو دا ضربی (multiple) ہووے، نو بلاکاں وچ ونڈیا جا سکدا اے۔

اصلی پر بہت نِکا

لکھاری فائدے لئی کوئی عدد نہیں دیندے۔ اوہ مستقل عدداں نوں ایس طرح بیان کردے نیں کہ اوہ «بغیر سدھار دے نہایت نِکے توں لے کے وڈے سدھاراں نال بس نِکے تیکر» نیں۔ گل عملی رفتار دی نہیں: گل ایہہ اے کہ دہاکیاں توں منّی جان والی اک رکاوٹ موجود ای نہیں۔

نتیجے کلیکاں توں اگے تیکر جاندے نیں۔ Max-Cut تے Max-2-SAT ورگے اوکھے سدھار (optimisation) مسئلیاں لئی ٹھیک ٹھیک حل کڈھن والے (exact) الگورتھم، جو n متغیراں (variables) لئی لگ بھگ 2^(ωn/3) قدماں وچ چلدے سن، ہُن اوہناں نوں وی اک چھوٹا قوت نما مل جاندا اے۔ کسے وی مقرر نِکے گراف دیاں نقلاں گنن نال وی ایہو ہوندا اے۔

اے آئی نے کیہ کیتا

اک وکھرے حصے وچ، لکھاری دسدے نیں کہ اوہناں نے ChatGPT-6 نال کیویں کم کیتا، جیہنوں اوہدے عوامی ویب انٹرفیس راہیں ورتیا گیا۔ پنج بندیاں دیاں کلیکاں لئی اپنے خیالاں توں، تے OpenAI دے اک حالیہ نتیجے توں جو اک ہور قیاس (conjecture)، قوت نمائی ویلے دے مفروضے (Exponential Time Hypothesis)، نوں رد کردا اے، شروع کر کے، ماڈل نے 5-کلیکاں لئی اک پہلا، پیچیدہ سدھار لبھیا۔ فیر لکھاریاں نے، اے آئی دی مدد نال، اوہنوں نچوڑ کے ثبوت دے دل وچ موجود الجبری ونڈ (algebraic decomposition) بنا دتی، جیہنوں اوہ «لگ بھگ پوری طرح اے آئی دا حصہ» سمجھدے نیں۔ اوہدے دوالے اُساریا گیا الگورتھمی ڈھانچہ، اوہناں دے مطابق، بہتا اوہناں دا اپنا اے۔

اک گل خاص طور اُتے نمایاں اے۔ لکھاری نوٹ کردے نیں کہ اے آئی دے بنائے دھندلے (obscure) ثبوت انساناں لئی پڑھنے اوکھے نیں — تے اوہناں نوں ایس گل نے «متاثر کیتا کہ ایہہ آپ اے آئی لئی وی سمجھنے اوکھے نیں»۔