کمپیوٹنگ اور مصنوعی ذہانتپری پرنٹنظریہ4 منٹ کا مطالعہ

کلیکوں کی تلاش کی رفتار کی حد 40 سال بعد ٹوٹ گئی

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

1985 کی ایک ترکیب اور ایک طویل چیلنج

40 سال سے زیادہ پہلے، Jaroslav Nešetřil اور Svatopluk Poljak نے ایک مختصر راستہ ڈھونڈ نکالا۔ انہوں نے k-کلیک کی تلاش کو ایک بڑے گراف میں ایک مثلث کی تلاش میں بدل دیا، جو بدلے میں میٹرکسوں کی ضرب (multiplying matrices)، یعنی اعداد کے بڑے جدولوں کی ضرب، کے ذریعے کی جا سکتی ہے۔ لاگت ω پر منحصر ہے، جو میٹرکس ضرب کا قوت نما (exponent) ہے: ان کا طریقہ تقریباً n^(ωk/3) قدم لیتا ہے۔ ω کی ٹھیک قدر کوئی نہیں جانتا۔ یہ کم از کم 2 ہے، اور مضمون اس کی ایک حالیہ بالائی حد 9/4 کا حوالہ دیتا ہے۔

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

ایک متحرک ہدف

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

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

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

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

تبادلے کم کناروں والے سادہ تر نمونے دیتے ہیں، جنہیں دوبارہ اسی طریقے سے نمٹایا جاتا ہے؛ نو راسوں والے نمونے میں زیادہ سے زیادہ 36 کنارے ہوتے ہیں، اس لیے یہ تکرار (recursion) ختم ہو جاتی ہے۔ کم رتبے والا بقیہ ضرب دیے جانے والے میٹرکسوں کو چھوٹا کر دیتا ہے۔ یہ ترکیب ایک ساتھ دو الگ الگ ویجوں پر لاگو کرنا ہی وہ چیز ہے جو ω = 2 ہونے پر بھی فائدہ برقرار رکھتی ہے۔ پھر نو کے کسی بھی مضرب k کو نو بلاکوں میں گروہ بند کیا جا سکتا ہے۔

حقیقی مگر ننھا

مصنفین فائدے کے لیے اعداد نہیں دیتے۔ وہ مستقلات کو “بغیر اصلاح کے نہایت حقیر سے لے کر نمایاں اصلاحات کے ساتھ ننھے تک” قرار دیتے ہیں۔ نکتہ عملی رفتار نہیں: نکتہ یہ ہے کہ دہائیوں سے مانی جانے والی ایک رکاوٹ موجود ہی نہیں۔

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

مصنوعی ذہانت نے کیا کیا

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

ایک تبصرہ نمایاں ہے۔ مصنفین نوٹ کرتے ہیں کہ مصنوعی ذہانت کے تیار کردہ مبہم ثبوت انسانوں کے لیے پڑھنا مشکل ہوتے ہیں — اور انہیں یہ بات “متاثر کن لگی کہ انہیں سمجھنا خود مصنوعی ذہانت کے لیے بھی مشکل ہے”۔