رایانش و هوش مصنوعیپیش‌چاپنظریه۳ دقیقه مطالعه

حد سرعت یافتن خوشه‌ها پس از 40 سال فرو ریخت

یک شبکهٔ اجتماعی با n نفر را در نظر بگیرید. آیا گروهی k نفری از آن‌ها هست که همه یکدیگر را بشناسند؟ دانشمندان علوم رایانه چنین گروهی را k-خوشه (k-clique) می‌نامند و یافتن آن مسئله‌ای کلاسیک با کاربردهای بی‌شمار است. روش ساده‌لوحانه همهٔ گروه‌های ممکنِ k نفری را بررسی می‌کند، که تقریباً n^k گروه است — برای شبکه‌های بزرگ ناامیدکننده.

ترفندی از 1985 و چالشی طولانی

بیش از 40 سال پیش، یاروسلاو نشتریل (Jaroslav Nešetřil) و سواتوپلوک پولیاک (Svatopluk Poljak) میان‌بری یافتند. آن‌ها جست‌وجوی یک k-خوشه را به جست‌وجوی یک مثلث در گرافی بزرگ‌تر تبدیل کردند، که آن نیز به نوبهٔ خود با ضرب ماتریس‌ها، یعنی جدول‌های بزرگی از عددها، انجام‌شدنی است. هزینه به ω، نمای ضرب ماتریس، بستگی دارد: روش آن‌ها حدود n^(ωk/3) گام لازم دارد. هیچ‌کس مقدار دقیق ω را نمی‌داند. ω دست‌کم 2 است و مقاله یک کران بالای تازه به اندازهٔ 9/4 را نقل می‌کند.

نمای آن روش 1985 هرگز شکسته نشد. در 2004، گرهارد ووگینگر (Gerhard Woeginger) پژوهشگران را به چالش کشید تا برای یک k ثابت بهتر عمل کنند؛ بیش از دو دهه گذشت. در این میان فرضیهٔ k-خوشه (k-Clique Hypothesis) — اینکه n^(ωk/3) در اصل بهترین مقدار ممکن است — به یکی از پایه‌های «پیچیدگی ریزدانه» (fine-grained complexity) تبدیل شد. پژوهشگران از آن بهره گرفتند تا استدلال کنند که بسیاری از مسئله‌های دیگر، از تجزیهٔ دستور زبان‌ها تا تحلیل داده‌های فشرده، نیز نمی‌توانند سریع‌تر حل شوند.

هدفی متحرک

رد این فرضیه دشواری ویژه‌ای داشت. هزینهٔ پیش‌بینی‌شده‌اش به ω بستگی دارد که ناشناخته است. الگوریتمی که بهترین مقدار کنونی ω را پشت سر بگذارد، اگر کسی بعدها ضرب ماتریس سریع‌تری بیابد، ممکن است دیگر از فرضیه پیشی نگیرد.

ویرجینیا واسیلفسکا ویلیامز (Virginia Vassilevska Williams) از MIT و اُر زامیر (Or Zamir) از دانشگاه تل‌آویو این مشکل را دور می‌زنند. آن‌ها اثبات می‌کنند که برای هر k به اندازهٔ کافی بزرگ، یک k-خوشه را می‌توان در حدود n^((ω/3 − c)k) گام یافت — و حتی شمرد — که در آن c ثابتی مثبت است که نه به k بستگی دارد و نه به ω. این صرفه‌جویی نسبت به مقدار واقعی ω سنجیده می‌شود، هر چه که از آب درآید. حتی اگر ω = 2 باشد، یعنی بهترین حالت قابل‌تصور، پابرجا می‌ماند.

تاکردن یک گوه

قلب این روش به الگوهای نُه‌رأسی مربوط است. رویکرد استاندارد آن‌ها را به سه گروه سه‌تایی تقسیم می‌کند و سه ماتریس عظیم را در هم ضرب می‌کند. نویسندگان به یک گوه (wedge) — دو یال با یک رأس مشترک — می‌نگرند و میان دو ماتریس جدولی می‌گذارند که هیچ چیزی را تغییر نمی‌دهد: ماتریس همانی. سپس این ماتریس همانی را به صورت مجموعی از چند «جابه‌جایی» (swap) می‌نویسند، که هر یک دو یال گوه را در یک یال ادغام می‌کند، به‌علاوهٔ باقی‌مانده‌ای با رتبهٔ پایین.

جابه‌جایی‌ها الگوهای ساده‌تری با یال‌های کمتر می‌دهند که باز با همان روش پردازش می‌شوند؛ یک الگوی نُه‌رأسی دست‌بالا 36 یال دارد، پس این بازگشت به پایان می‌رسد. باقی‌ماندهٔ کم‌رتبه ماتریس‌هایی را که باید ضرب شوند کوچک می‌کند. به‌کاربستن این ترفند هم‌زمان روی دو گوهٔ جداگانه همان چیزی است که حتی وقتی ω = 2 باشد برتری را حفظ می‌کند. سپس هر k که مضربی از نُه باشد را می‌توان در نُه بلوک گروه‌بندی کرد.

واقعی اما بسیار ناچیز

نویسندگان برای این برتری عددی ارائه نمی‌کنند. آن‌ها ثابت‌ها را چنین توصیف می‌کنند: «از ناچیز بدون بهینه‌سازی تا بسیار کوچک با بهینه‌سازی‌های چشمگیر». نکته سرعت در عمل نیست: نکته این است که مانعی که ده‌ها سال به آن باور داشتند وجود ندارد.

پیامدها از خوشه‌ها فراتر می‌روند. الگوریتم‌های دقیق برای مسئله‌های بهینه‌سازی دشواری مانند Max-Cut و Max-2-SAT، که برای n متغیر در حدود 2^(ωn/3) گام اجرا می‌شدند، اکنون نمای کوچک‌تری هم می‌گیرند. شمردن نسخه‌های هر گراف کوچک ثابت نیز همین‌طور.

آنچه هوش مصنوعی انجام داد

نویسندگان در بخشی جداگانه شرح می‌دهند که چگونه با ChatGPT-6 کار کردند که از راه رابط وب عمومی‌اش به کار گرفته شد. مدل، با آغاز از ایده‌های خود آن‌ها برای خوشه‌های پنج‌نفره و از نتیجه‌ای تازه از OpenAI که حدس دیگری، یعنی فرضیهٔ زمان نمایی (Exponential Time Hypothesis)، را رد می‌کرد، نخستین بهبود پیچیده را برای 5-خوشه‌ها یافت. سپس نویسندگان، با کمک هوش مصنوعی، آن را به تجزیهٔ جبری‌ای که در هستهٔ اثبات قرار دارد پالایش کردند و آن را «تقریباً به‌طور کامل سهم هوش مصنوعی» می‌دانند. به گفتهٔ آن‌ها، چارچوب الگوریتمی‌ای که پیرامون آن ساخته شده عمدتاً کار خودشان است.

یک نکته برجسته است. نویسندگان یادآوری می‌کنند که خواندن اثبات‌های مبهمی که هوش مصنوعی تولید می‌کند برای انسان‌ها دشوار است — و آن‌ها «شگفت‌زده شدند که فهمیدن این اثبات‌ها برای خود هوش مصنوعی هم دشوار است».