نقدم أول تحسينات متعددة الحدود على الخوارزميات القياسية لـ 3SUM وأقصر المسارات بين جميع الأزواج (APSP): نعرض كيفية حل 3SUM حتميًا على n أعداد صحيحة بحجم متعدد الحدود في زمن O(n^{1.9992}) وAPSP على رسوم بيانية موجهة برؤوس n بأوزان صحيحة محدودة متعددة الحدود في زمن O(n^{2.9995}). هذا يدحض فرضيات 3SUM وAPSP. باستخدام اختزالات معروفة، ندحض أيضًا النسخ ذات القيمة الحقيقية لفرضيات 3SUM وAPSP، وفرضية المثلث الدقيق، وفرضيات k-زمرة ذات الوزن الصفري، والتخمينات الثلاثة المستطيلة الموجهة لمصفوفة-متجه عبر الإنترنت لـ van den Brand وNanongkai وSaranurak، ونقدم تسريعات متعددة الحدود لمجموعة متنوعة من المشكلات الأخرى. كل هذه النتائج تتبع من خوارزمية جديدة واحدة لمنتجات المصفوفات الرقيقة. لتكن X مصفوفة أعداد صحيحة N×D وY مصفوفة أعداد صحيحة D×N مع D ≤ N^{1/18}، ولتكن W أي مجموعة من على الأكثر N^2/√D موضعًا. نحسب الإدخالات (XY)[I, J]، (I, J)∈W، في O(N^2/D^{0.063}) عملية، وهو أقل متعدد الحدود من الوقت اللازم لكتابة XY أو لحساب N^2/√D منتجًا داخليًا واحدًا تلو الآخر. نصمم هذه الخوارزمية بتعديل متغير من خوارزمية ضرب المصفوفات المستطيلة لـ Coppersmith، المبنية من هوية عشر عمليات ضرب لـ Schönhage، لتنفيذ العمليات اللازمة فقط للإدخالات في W، ونظهر أن هناك حاجة لعمليات قليلة. عند تفسيرها كخوارزمية رسم بياني، تحل هذه مشكلة المثلث المتناثر لجميع الحواف في زمن شبه تربيعي حقيقي على رسوم بيانية ثلاثية الأجزاء متناثرة غير متوازنة حيث يحتوي جزءان على n رؤوس لكن جزءًا واحدًا يحتوي على n^{ε} رؤوس لـ ε<0.12. بواسطة اختزالات معروفة، المثلث الدقيق، وبالتالي 3SUM وAPSP، تختزل إلى هذه المشكلة. نقدم أيضًا نسخة بنية بيانات تجيب على استعلامات لإدخالات فردية من XY، غير معروفة مسبقًا. تاريخ التقديم: من Josh Alman [عرض البريد الإلكتروني] [v1]الاثنين، 5 أكتوبر 2026 17:44:29 UTC (93 كيلوبايت)
المصدر: Hacker News · لخّصه HeadlinesBriefing