💻 علوم الحاسوب

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

تقدم هذه الورقة أول التحسينات متعددة الحدود على الخوارزميات التقليدية لمسألتي 3SUM وAll-Pairs Shortest Paths (APSP) من خلال تقديم خوارزمية مبتكرة لحساب المدخلات المتفرقة لضرب المصفوفات في الرسوم البيانية غير المتماثلة، مما يدحض فرضيتي 3SUM وAPSP ويحقق تسريعاً للعديد من المسائل ذات الصلة.

المؤلفون الأصليون: Josh Alman, Virginia Vassilevska Williams

نُشر 2026-10-06

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Josh Alman, Virginia Vassilevska Williams

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

في المشهد الواسع لعلوم الحاسوب، توجد مشكلات قاومت التحسين بعناد لعقود من الزمن، حيث عملت كمطبات تعيق قدرتنا على معالجة المعلومات بشكل أسرع. اثنتان من أشهر هذه المشكلات هما مشكلة "المجموع الثلاثي" (three-sum) ومشكلة "أقصر المسارات بين جميع الأزواج" (all-pairs shortest paths). تسأل الأولى سؤالاً بسيطاً: إذا أُعطيت قائمة من الأرقام، هل يمكنك إيجاد ثلاثة منها مجموعها يساوي صفراً؟ لفترة طويلة، كانت أفضل طريقة لحل هذه المشكلة لقائمة كبيرة من الأرقام تستغرق وقتاً ينمو مع مربع حجم القائمة. أما المشكلة الثانية، فتطلب معرفة أقصر مسافة بين كل زوج من المدن في شبكة من الطرق. لطالما استغرقت أفضل طريقة معروفة لها وقتاً ينمو مع مكعب عدد المدن. لسنوات، اعتقد علماء الحاسوب أن هذه الحدود غير قابلة للكسر، مما شكل مجموعة من القواعد تسمى "فرضيات" تشير إلى أنه لا يمكن لأي خوارزمية أن تكون أسرع بكثير من هذه الطرق المذكورة في الكتب المدرسية. هذه المشكلات ليست مجرد ألغاز مجردة؛ فهي تدعم كل شيء بدءاً من برامج الخرائط وصولاً إلى اكتشاف الأنماط في البيانات المعقدة، لذا فإن إيجاد طريقة لكسر حدود السرعة هذه سيكون تحولاً هائلاً في كيفية الحوسبة لدينا.

لقد تمكن فريق من الباحثين من جامعة كولومبيا ومعهد ماساتشوستس للتكنولوجيا (MIT)، بالتعاون مع نموذج ذكاء اصطناعي طورته شركة "أنثروبيك" (Anthropic)، من تحطيم هذه المعتقدات الراسخة. فقد اكتشفوا طريقة جديدة لحل هذه المشكلات أسرع حقاً من الطرق الأفضل السابقة. فبدلاً من استغراق وقت يتناسب مع مربع حجم المدخلات لمشكلة "المجموع الثلاثي"، تقوم طريقتهم الجديدة بحلها في وقت أقل قليست من المربع. وبالمثل، بالنسبة لمشكلة أقصر المسارات، فقد قللوا الوقت المطلوب إلى أقل قليلاً من مكعب عدد المدن. هذا ليس مجرد تعديل طفيف أو خدعة تعمل فقط في حالات خاصة؛ بل هو تحسين جوهري ينطبق على نطاق واسع من المدخلات. ومن خلال إثبات إمكانية حل هذه المشكلات بشكل أسرع، فقد دحض الباحثون فعلياً الفرضيات التي زعمت عدم إمكانية ذلك.

يكمن السر وراء هذا الإنجاز في نهج جديد ذكي لضرب المصفوفات، وهي ببساطة شبكات من الأرقام تُستخدم لتمثيل البيانات. ركز الباحثون على نوع محدد من ضرب المصفوفات حيث تكون الشبكات نحيفة وطويلة، بدلاً من أن تكون مربعة. وأدركوا أنه إذا كنت تحتاج فقط لمعرفة الإجابات لبعض المواضع المحددة في النتيجة النهائية، بدلاً من حساب كل رقم في الشبكة بأكملها، فيمكنك تجاوز كم هائل من العمل. لقد صمموا خوارزمية تعمل مثل مرشح عالي الكفاءة، حيث تتجاهل الحسابات التي ستنتج إجابات لم يطلبها أحد. تم بناء هذه التقنية عن طريق تعديل هوية رياضية قديمة، وهي مجموعة من القواعد لدمج الأرقام، لتعمل فقط على قطع المعلومات المحددة التي تهمنا.

تأتي قوة هذا الاكتشاف من كيفية ترابط مشكلات الحاسوب المختلفة هذه. في عالم التعقيد الدقيق (fine-grained complexity)، قضى الباحثون سنوات في رسم خرائط لكيفية مساعدة حل مشكلة واحدة في حل مشكلة أخرى. وقد وجدوا أنه إذا تمكنت من حل مشكلة "المجموع الثلاثي" بشكل أسرع، فيمكنك أيضاً حل مشكلة "أقصر المسارات" بشكل أسرع، والعكس صحيح. وتعمل الخوارزمية الجديدة كمفتاح رئيسي؛ فمن خلال فك شفرة مشكلة ضرب المصفوفات المحددة هذه، فتح الباحثون الطريق لحلول أسرع لعشرات المشكلات الأخرى التي كان يُعتقد سابقاً أنها عالقة عند سرعاتها القديمة. ويشمل ذلك العث find المثلثات في الشبكات، والتحقق من أنماط معينة في البيانات، وتحسين أنواع مختلفة من مهام البحث والفرز.

لم يكتف الفريق بإيجاد إمكانية نظرية فحسب، بل قدموا طريقة حتمية ملموسة تعمل في كل مرة. كما أظهروا أن نهجهم يعمل حتى عندما لا تكون الأرقام المعنية مجرد أعداد صحيحة، بل أعداداً حقيقية، وهي نوع القيم المستخدمة في معظم الحسابات العلمية في العالم الحقيقي. استخدم الباحثون أداة ذكاء اصطناعي قوية للمساعدة في التحقق من براهينهم الرياضية، مما يضمن أن المنطق وراء زيادة السرعة كان سليماً. يسلط هذا التعاون بين الباحثين البشر والذكاء الاصطناعي الضوء على عصر جديد في الاكتشاف العلمي، حيث يمكن للآلات المساعدة في كشف الحقائق الرياضية العميقة التي قد تفوت البشر.

إن تداعيات هذا العمل تمتد إلى ما هو أبعد من مشكلتي "المجموع الثلاثي" و"أقصر المسارات". فهو يتحدى فكرة أن بعض الحدود الحوسبية هي حدود مطلقة. لعدة عقود، تقبل المجتمع فكرة أن بعض المشكلات تتطلب وقتاً معيناً لحلها، وأن محاولة الذهاب بشكل أسرع كانت عبثاً. تثبت هذه الورقة أن تلك الحدود لم تكن جدراناً، بل كانت مجرد سقوف يمكن رفعها بالمنظور الصحيح. وبينما تعتبر الخوارزميات الجديدة حالياً معقدة للغاية بحيث يصعب استخدامها في البرمجيات اليومية بسبب الثوابت الخفية الهائلة في سرعتها، فإن إثبات وجودها يغير الأساس النظري لعلوم الحاسوب. إنه يفتح الباب أمام الباحثين المستقبليين لصقل هذه الأساليب، مما قد يؤدي إلى أدوات عملية يمكنها معالجة مجموعات البيانات الضخمة بكفاءة أكبر بكثير من أي وقت مضى. لقد أثبت الباحثون أن حتى أكثر المشكلات استعصاءً يمكن أن تخضع للتفكير الجديد، مما يثبت أن حدود ما يمكن حوسبته هي دائماً جديرة بالاختبار.

ملخص تقني: خوارزميات 3SUM وAPSP تحت التربيعية حقاً وعبر التثليث في الرسوم البيانية المتناثرة غير المتوازنة

1. بيان المشكلة

تتناول هذه الورقة مشكلتين أساسيتين في نظرية التعقيد دقيق التفاصيل (fine-grained complexity) استعصتا على التحسين الملحوظ لعقود:

3SUM: معطى $n$ من الأعداد الصحيحة ذات الحجم متعدد الحدود، حدد ما إذا كانت ثلاثة منها مجموعها صفر. تعمل الخوارزمية القياسية في زمن قدره $O(n^2)$ ، وتفترض فرضية 3SUM أنه لا توجد خوارزمية يمكنها حل هذه المشكلة في زمن $O(n^{2-\epsilon})$ لأي $\epsilon > 0$ .
APSP (أقصر مسار بين جميع الأزواج): معطى رسم بياني موجه بـ $n$ من الرؤوس وأوزان صحيحة محدودة متعددة الحدود، احسب أقصر مسار بين جميع أزواج الرؤوس. تعمل الخوارزميات القياسية (مثل Floyd-Warshall وJohnson) في زمن قدره $O(n^3)$ . تفترض فرضية APSP أنه لا توجد خوارزمية يمكنها حل هذه المشكلة في زمن $O(n^{3-\epsilon})$ .

تستهدف الورقة أيضاً مشكلة المثلث الدقيق (إيجاد مثلث بإجمالي وزن حواف يساوي صفراً في رسم بياني ثلاثي الأجزاء) ومشكلة APSP الموجه غير الموزون (Directed Unweighted APSP)، بالإضافة إلى مجموعة واسعة من المشكلات المكافئة لهما تحت اختزالات دقيقة التفاصيل (مثل: حاصل الضرب $(\min, +)$ ، مسافة تحرير الشجرة، وZero-Weight $k$ -Clique).

2. المنهجية

المساهمة الجوهرية هي تطوير خوارزمية جديدة لحساب مجموعة محددة متناثرة من المدخلات في حاصل ضرب مصفوفتين "نحيفتين".

2.1 خوارزمية حاصل ضرب المصفوفات النحيفة

يطور المؤلفون خوارزمية حتمية لحساب مجموعة $W$ من المدخلات في حاصل الضرب $XY$ ، حيث:

$X$ مصفوفة صحيحة بحجم $N \times D$ .
$Y$ مصفوفة صحيحة بحجم $D \times N$ .
$D \le N^{1/18}$ (المصفوفات "نحيفة").
$W$ هي مجموعة من $N^2/\sqrt{D}$ موقعاً كحد أقصى.

الابتكار التقني الرئيسي:
تقوم الخوارماجية بتعديل خوارزمية Coppersmith لضرب المصفوفات المستطيلة، والتي تعتمد هي نفسها على هوية الضرب العشرية لـ Sch¨onhage.

البنية التكرارية: تطبق الخوارزمية هوية Sch¨onage بشكل تكراري. وبخلاف ضرب المصفوفات القياسي الذي يحسب جميع مدخلات $N^2$ ، تقوم هذه الخوارزمية بتقليم شجرة التكرار.
استراتيجية التقليم: تزور الخوارزمية فقط "الأوراق" (leaves) في شجرة التكرار الضرورية لحساب المدخلات الموجودة في $W$ .
مشاركة الترميز: مرحلة "الترميز" (التركيبات الخطية لكتل المدخلات) تعتمد فقط على مصفوفات المدخلات، وليس على مدخلات المخرجات المحددة. تحسب الخوارزمية هذه الترميزات مرة واحدة لكل كتلة مدخلات وتشاركها عبر جميع الحسابات المطلوبة.
تحليل الأوراق: يحلل المؤلفون "ترتيب" الأوراق في شجرة التكرار. ويثبتون أنه بينما يتطلب مدخل مخرجات واحد العديد من الأوراق، فإن معظم الأوراق يتم مشاركتها بين العديد من مدخلات المخرجات. ومن خلال موازنة عدد أوراق الرتب المختلفة بعناية، يظهر لهم أن إجمالي عدد الأوراق المطلوبة لمجموعة $W$ متناثرة هو أصغر بكثير من تكلفة حساب حاصل الضرب الكامل أو حساب المدخلات بشكل فردي.

التعقيد:
تحسب الخوارزمية مدخلات $W$ في زمن قدره $O(N^2 / D^{0.063})$ (مع عوامل لوغاريتمية)، وهو أسرع بمقدار متعدد الحدود من زمن $O(N^2)$ المطلوب لكتابة حاصل الضرب الكامل أو $O(N^2 \sqrt{D})$ المطلوب لحساب المدخلات بشكل فردي كحاصل ضرب داخلي.

2.2 الاختزالات إلى مشكلات الرسوم البيانية

تُطبق خوارزمية المصفوفات على مشكلة Lopsided All-Edges Sparse Triangle. في هذه المشكلة، يسعى المرء لتحديد ما إذا كانت مجموعة من الحواف $(a, b)$ في رسم بياني ثلاثي الأجزاء (بأجزاء $A, B$ بحجم $n$ وجزء أوسط $M$ بحجم $D \ll n$ ) تقع ضمن مثلث.

التفسير المصفوفي: هذا يكافئ حساب مدخلات حاصل ضرب مصفوفات التجاور الثنائية للرسم البياني في المواقع المقابلة للحواف في $W$ .
الاختزال الحتمي: تقدم الورقة اختزالاً حتمياً من Exact Triangle (في الرسوم البيانية العامة) إلى Lopsided All-Edges Sparse Triangle. يتضمن ذلك تشفير أوزان الحواف باستخدام دالة هاش (hash) بمقاس (modulo) عدد أولي يتم اختياره حتمياً لتقليل الإيجابيات الكاذبة، متبوعاً بالبحث عن الشاهد (witness).
سلسلة الاختزالات: تربط الاختزالات المعروفة في دقة التفاصيل بين 3SUM و APSP وبين Exact Triangle. ومن خلال دمج هذه الاختزالات مع الخوارزمية الجديدة لـ Lopsided All-Edges Sparse Triangle، يستنتج المؤلفون خوارزميات أسرع للمشكلات الأصلية.

3. المساهمات والنتائج الرئيسية

3.1 دحض الفرضيات

تقدم الورقة أول تحسينات متعددة الحدود على الخوارزميات التقليدية لـ 3SUM وAPSP، مما يدحض فرضيتي 3SUM وAPPS في نظرية التعقيد دقيق التفاصيل.

3SUM: حُلَّت حتمياً في زمن $O(n^{1.9992})$ للأعداد ذات الحجم متعدد الحدود.
APSP: حُلَّت حتمياً في زمن $O(n^{2.9995})$ للرسوم البيانية الموجهة ذات الأوزان المحدودة متعدد الحدود.
Exact Triangle: حُلَّت حتمياً في زمن $O(n^{2.9983})$ .
Directed Unweighted APSP: حُلَّت حتمياً في زمن $O(n^{2+\mu-\epsilon})$ (حيث $\mu < 0.5275$ )، مما يدحض فرضية أن خوارزمية Zwick هي الأمثل. هذا هو أول تحسين لم يُشتق فقط من حدود ضرب المصفوفات المستطيلة الأسرع.

3.2 المتغيرات ذات القيم الحقيقية

باستخدام اختزال من Chan وVassilevska Williams وXu يعتمد فقط على المقارنات والجمع والطرح، يقدم المؤلفون خوارزميات Las Vegas (عشوائية ذات خطأ صفري) للنسخ ذات القيم الحقيقية من هذه المشكلات:

Real 3SUM: زمن متوقع $O(n^{1.998})$ .
Real APSP: زمن متوقع $O(n^{2.998})$ .

3.3 التأثير الخوارزمي الأوسع

من خلال الاختزالات المعروفة، تؤدي التقنية الجديدة إلى تسريع العديد من المشكلات الأخرى، بما في ذلك:

حاصل الضرب $(\min, +)$ للمصفوفات.
مسافة تحرير الشجرة (للتكاليف الصحيحة المحدودة متعدد الحدود).
Zero-Weight, Min-Weight, and Max-Weight $k$ -Clique لأي ثابت $k \ge 3$ .
تخمينات Online Matrix-Vector (OMv): تدحض الورقة النسخ "الملمّحة" (hinted) من تخمين OMv (تحديداً للملمات النحيفة) من خلال توفير بنية بيانات تعالج المصفوفات في زمن تحت-تربيعي وتجيب على استعلامات المدخل الواحد في زمن تحت-خطي بالنسبة للبعد الداخلي.
Knapsack و Approximate Subset Sum: أول خوارزميات تحت-تربيعية حقاً لـ Unbounded Knapsack ومخططات تقريبية لـ Subset Sum.

3.4 نسخة بنية البيانات

يمدد المؤلفون خوارزمية المصفوفات إلى بنية بيانات. بعد المعالجة المسبقة لـ $X$ و $Y$ في زمن $O(N^2/D^{0.063})$ ، يمكن حساب أي مدخل فردي $(XY)[I, J]$ في زمن $O(D^{0.437})$ . يسمح هذا بحل المشكلات التي لا تكون فيها المدخلات المستهدفة معروفة مسبقاً.

4. الأهمية والادعاءات

يرى المؤلفون أن هذا العمل هو "نجاح كبير لتعقيد التفاصيل الدقيقة".

الاختزالات كخوارزميات: تؤكد الورقة أن اختزالات التفاصيل الدقيقة، التي كانت تُستخدم سابقاً لاستنتاج الصعوبة الشرطية فقط، هي أيضاً خوارزميات. يمكن لتقنية واحدة جديدة (خوارزمية حاصل ضرب المصفوفات النحيفة) أن تسرع في آن واحد شبكة واسعة من المشكلات المترابطة.
دحض الوضع الراهن: تظهر النتائج أن أوقات التشغيل "العالقة" لـ 3SUM وAPSP لم تكن عوائق جوهرية بل كانت نتاجاً للتقنيات المتاحة في ذلك الوقت.
القيود والأسئلة المفتوحة:
- يشير المؤلفون إلى أن تقنياتهم لا تحسن حالياً CNF-SAT، أو Orthogonal Vectors، أو $k$ -SUM لـ $k \ge 4$ ، لأن هذه المشكلات لا تختزل إلى حالات المثلث المتناثرة المحددة التي تم حلها هنا.
- الخوارزميات جبرية ولها حالياً ثوابت مخفية كبيرة، مما يجعلها غير عملية للاستخدام المباشر في العالم الحقيقي.
- حالة التوازن لـ All-Edges Sparse Triangle (حيث تكون جميع الأجزاء الثلاثة بحجم $n$ ) لا تزال غير محلولة بهذه التقنية، مما يترك فرضية $m^{4/3}$ قائمة لهذا النوع المحدد.
- لا تدعي الورقة أنها وجدت الأسس المثلى لهذه المشكلات، مشيرة إلى أن التحسينات الإضافية قد تكون ممكنة من خلال اختزالات أفضل أو هويات جبرية أكثر دقة.

5. ملاحظة منهجية حول الاكتشاف

توضح الورقة صراحة أن الخوارزمية الجوهرية تم اكتشافها بواسطة Claude، وهو نموذج ذكاء اصطنا-ئي طورته Anthropic. عمل المؤلفون (Josh Alman وVirginia Vassilevska Williams) على فهم وتبسيط وتقوية وتوسيع الخوارزمية، واستنباط النتائج، وصياغة النتائج رسمياً. تم التحقق من النتائج الرئيسية باستخدام مساعد الإثبات Lean 4. يتحمل المؤلفون المسؤولية الكاملة عن محتوى الورقة وعرضها.