الحوسبة والذكاء الاصطناعي · التجربة
تجاوز الحدّ
شبكة، ومجموعة من أشخاص يعرف بعضهم بعضًا جميعًا، وطريق مختصر من عام 1985 عبر ضرب المصفوفات، وفرضية صمدت عقودًا. أربعة أسئلة، من المبتدئ إلى الخبير، عن نهاية فرضية عُصبة k.
1 · اذكر ما بُرهن
مبتدئ
ماذا يُظهر المقال بشأن فرضية عُصبة k؟
2 · احسب كلفة 1985
تجد طريقة نيشيتريل–بولياك عُصبة k في نحو n^(ωk/3) خطوة. خذ k = 9 وω = 2، وهي أدنى قيمة يمكن أن تأخذها ω.
متوسط
ما أُسّ n الذي تعطيه طريقة 1985؟
3 · اشرح «حتى لو كانت ω = 2»
تتنبأ الفرضية بكلفة قدرها n^(ωk/3). والقيمة الدقيقة لـω مجهولة: فهي لا تقل عن 2، ويستشهد المقال بحدّ أعلى قدره 9/4.
خبير
لماذا يهم أن يصمد التوفير الجديد أيًّا كانت ω، حتى ω = 2؟
4 · انقل المكسب
كانت Max-2-CSP، التي تشمل Max-Cut وMax-2-SAT، على n متغيرًا بوليانيًا، تُحل في نحو 2^(ωn/3) خطوة. قسّم المتغيرات إلى تسع مجموعات، فيصبح كل إسناد لقيم مجموعةٍ رأسًا في مسألة عُصبة تسعة موزونة.
خبير
ماذا تعطي خوارزمية العُصَب الجديدة لهذه المسائل؟
هُزم الحدّ
—