تشكيل الفرق باستخدام رياضيات عدم التوازن

احصل على آخر الأخبار مباشرة إلى بريدك الوارد.

منشور مستقل تحريريًا مدعوم من مؤسسة سايمونز (Simons Foundation).

اكتب مصطلح(مصطلحات) البحث واضغط على "إدخال" (Enter)

• حفظ المقال اقرأ لاحقًا اقرأ لاحقًا

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

إذن، ما مدى توازن فرقك عند تجميعها بحيث تمتلك قوة متكافئة في كل فئة، من الأساطير اليونانية إلى كرة السلة الجامعية؟

يمكنك دائمًا جعل الفرق متكافئة بشكل مدهش، وفقًا لباحثين يدرسون نظرية التناقض التركيبي (combinatorial discrepancy theory).

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

في أوائل الثمانينيات، توصل عالم الرياضيات يانوش كوملوس (János Komlós) إلى تنبؤ غير بديهي. افترض أنه بغض النظر عن عدد الكائنات (لاعبيك) أو الأبعاد (فئات المعلومات العامة) التي تأخذها في الاعتبار، فإن التناقض — الذي يمكنك قياسه كميًا — لن يتجاوز أبدًا مقدارًا ثابتًا. ستكون هناك دائمًا طريقة لتقسيم الفرق بتناقض أقل من هذا المقدار المحدد.

"هذا أمر مذهل حقًا"، قال هاوتيان جيانغ (Haotian Jiang)، عالم الكمبيوتر النظري في جامعة شيكاغو (University of Chicago). "تقول فرضية كوملوس إن الأمر لا يتعلق ببعد المشكلة. إنه ثابت عالمي."

لم يجد أحد طريقة لدحض هذه الفرضية قط. ومع ذلك، فهي مذهلة لدرجة أن بعض علماء الرياضيات ظنوا أنها يجب أن تكون خاطئة. "إثباتها هو إحدى مشاكل الكأس المقدسة في نظرية التناقض"، قال نيخيل بانسال (Nikhil Bansal)، عالم الكمبيوتر النظري من جامعة ميشيغان (University of Michigan).

حتى واضع الفرضية يعتقد أنها سخيفة نوعًا ما. "كنت شابًا وأحمق عندما وضعتها"، مازح كوملوس (Komlós) المتقاعد الآن في رسالة بريد إلكتروني. "لقد ألقيت حجر عثرة في نظرية التناقض التركيبي بهذه الفرضية غير المسؤولة."

إذا كانت فرضية كوملوس صحيحة، يمكن أن تفتح حلولًا للعديد من المشاكل الأخرى، سواء داخل نظرية التناقض أو في مجالات مثل بحوث العمليات (operations research).

ولكن لعقود، بدا إثباتها أمرًا بعيد المنال. لم يتمكن علماء الرياضيات من إحراز تقدم كبير؛ كان أفضل حد أعلى للتناقض، الذي تحقق في عام 1998، لا يزال يعتمد بقوة على بُعد المشكلة. وكان بعيدًا عن أن يكون ثابتًا.

ثم، في خريف عام 2025، أعلن بانسال (Bansal) وجيانغ (Jiang) عن أول تقدم كبير في المشكلة منذ ما يقرب من 30 عامًا. لقد وجدوا حدًا يتغير ببطء شديد مع البُعد لدرجة أنه يكاد يكون ثابتًا، حتى مع عدد فلكي من الأبعاد. وصف باحثون آخرون هذا العمل، الذي استخدم منهجًا خوارزميًا مبتكرًا، بأنه "مثير للغاية"، و"نتيجة جميلة"، و"خطوة عملاقة إلى الأمام".

بينما لم يحل الاكتشاف غير المتوقع المشكلة بشكل كامل، فإنه يقدم أقوى دليل حتى الآن على أن فرضية كوملوس (Komlós) لم تكن غير مسؤولة بعد كل شيء. "كنت أميل إلى الاعتقاد بأن الفرضية خاطئة"، قال ألكسندر نيكولوف (Aleksandar Nikolov)، عالم الكمبيوتر في جامعة تورنتو (University of Toronto). العمل الجديد "يجعلني الآن أكثر ثقة بأن الفرضية صحيحة على الأرجح."

يوضح حل بانسال (Bansal) وجيانغ (Jiang) كيف يمكن تحويل الأنظمة المعقدة بشكل لا يصدق إلى شيء أبسط وأسهل للدراسة بكثير — ويقدم رؤى لها تطبيقات محتملة في الرياضيات والفيزياء وحتى التعلم الآلي.

تتعامل مشاكل التناقض، مثل مشكلة كوملوس (Komlós)، مع تقسيم مجموعات من الكائنات إلى مجموعتين فرعيتين. يمكنك التفكير في تقسيم الأشخاص إلى فرق معلومات عامة، أو السيارات المستعملة إلى دفعات، أو المشاركين في التجارب السريرية إلى مجموعات العلاج والعلاج الوهمي.

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

لنفترض أنك تهتم فقط بمجالين من المعرفة العامة — الكتب والأفلام. إليك كيف يمكنك تخيل كل شخص كمتجه:

الآن، خصص كل متجه لفريق. إذا وضعت متجهًا في الفريق (أ)، فاترك إحداثياته كما هي. إذا وضعته في الفريق (ب)، فاضرب كل إحداثياته بـ (1-). (هذا يعكس المتجه).

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

لكن الكمال لا يكون ممكنًا عادةً. لذا يصبح السؤال: إلى أي مدى يمكنك الاقتراب من الصفر؟

في مثالنا المكون من أربعة لاعبين، من السهل استعراض جميع الخيارات. إذا فعلت ذلك، ستجد أن أليس (Alice) وبوب (Bob) يجب أن يكونا في فريق واحد، وكارلا (Carla) وديف (Dave) في الفريق الآخر. (من الجدير بالذكر أنك لا تحتاج إلى أن يكون للفرق نفس عدد الأشخاص: أنت فقط تريد تقسيم المتجهات، بضرب أكبر عدد ممكن بـ (1-) حسب الحاجة، بحيث يلغي المتجهات بعضها البعض.)

تصبح هذه المهمة أصعب بكثير عندما يكون لديك المزيد من المتجهات والمزيد من السمات التي ترغب في موازنتها. ومع ذلك، كان لدى كوملوس (Komlós) فرضية متفائلة بشكل خاص: أنه بغض النظر عن عدد المتجهات أو السمات التي تأخذها في الاعتبار، يجب أن تكون هناك دائمًا طريقة لتقسيم المتجهات بحيث يكون المجموع أقل من الثابت العالمي نفسه.

في الواقع، يبدو أن هذه الفرضية بعيدة عن الصحة. فكر في استراتيجية ساذجة واحدة: ببساطة خصص المتجهات للفرق عشوائيًا. هذا يؤدي إلى تناقض يتصاعد بشكل كبير مع زيادة عدد المتجهات، N. في عام 1985، وجد جويل سبنسر (Joel Spencer) حدًا أفضل، حيث حدد التناقض دون لوغاريتم N؛ في عام 1998، حسّن فويتشخ باناستشيك (Wojciech Banaszczyk) الحد إلى $latex \sqrt{\log N}$، والذي يمكن كتابته أيضًا كـ log(N) ½. كانت كلتاهما خطوات ذات مغزى، لكن مقدار عدم التوازن استمر في النمو مع زيادة عدد المتجهات. بدا ثابت كوملوس (Komlós) بعيد المنال.

عندها بدأ علماء الكمبيوتر في الانخراط.

في أواخر العقد الأول من القرن الحادي والعشرين، بدأت مشاكل التناقض تجذب انتباه علماء الكمبيوتر النظريين. كان بانسال (Bansal) من بينهم. كان يأمل في إحراز تقدم في مشكلة كوملوس (Komlós) عن طريق كتابة سلسلة من الخطوات المنطقية — خوارزمية — يمكن للكمبيوتر تنفيذها نظريًا.

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

في عام 2010، توصل إلى فكرة لخوارزمية. بدأ بتقسيم كل متجه إلى نصفين. على سبيل المثال، إذا كان متجه أليس (Alice) هو <1, 0>، فسيرسل <½, 0> إلى الفريق (أ) و <½, 0> إلى الفريق (ب). "كان بإمكاني تقسيم شخص إلى اثنين"، قال بانسال (Bansal). ثم استخدم إجراءً عشوائيًا لمعالجة كل نصف متجه تدريجيًا بحيث ينتهي المطاف بفريق واحد بمتجه <1, 0> الأصلي بالكامل إلى جانبه. وفي كل خطوة، حرص على عدم السماح للتناقض بالانتفاخ كثيرًا.

أثبت أن خوارزميته، إذا طُبقت على جهاز كمبيوتر، يمكنها تقسيم المتجهات بحيث لا يتجاوز تناقضها نفس حد لوغاريتم (N) الذي وجده سبنسر (Spencer). "لم يتخيل أحد حتى أن ذلك ممكن"، قال راغو ميكا (Raghu Meka)، عالم الكمبيوتر الذي يعمل على خوارزميات التناقض في جامعة كاليفورنيا، لوس أنجلوس (University of California, Los Angeles). "لقد كان ذلك مبتكرًا تمامًا."

في عام 2016، عدّل بانسال (Bansal) خوارزميته لتتوافق مع حد باناستشيك (Banaszczyk) وهو log(N) ½ — الرقم القياسي القائم.

ألهم هذا العمل باحثين آخرين للتفكير في مشاكل التناقض بطريقة جديدة. "كما أنه قدم طريقة جديدة لمشكلة لم يكن لدى الناس أي مقاربات لها"، قال ميكا (Meka).

ومع ذلك، قال بانسال (Bansal)، "كعلماء كمبيوتر، كنا نلحق بهذه النتائج التي نعلم أن علماء الرياضيات الأذكياء قد أثبتوها بالفعل". وتساءل الآن عما إذا كان بإمكانه تطوير هذه الطريقة الجديدة أكثر — لا لمجرد معادلة الأرقام القياسية القديمة بل لتحديد أرقام جديدة.

في عام 2019، التقى بانسال (Bansal) بـ هاوتيان جيانغ (Haotian Jiang)، الذي كان آنذاك طالب دراسات عليا في جامعة واشنطن (University of Washington)، في مؤتمر. تقارب عالما الكمبيوتر بسبب اهتمامهما بخوارزميات التناقض، وبعد بضع سنوات، أثبتوا، بالتعاون مع ميكا (Meka) وباحثين آخرين، فرضية كوملوس (Komlós)، ولكن فقط في ظل ظروف محددة. استمتع بانسال (Bansal) وجيانغ (Jiang) بالعمل معًا وقررا مواصلة التعاون على الفرضية الكاملة.

"لدينا كيمياء جيدة"، قال بانسال (Bansal). "يمكنني أن أرمي عليه أفكارًا غير مكتملة، وهو يلتقطها. وهو يستطيع فعل الشيء نفسه."

في فبراير 2025، زار جيانغ (Jiang) بانسال (Bansal) لمدة أسبوع في آن أربور (Ann Arbor). بحلول اليوم الثاني، كان لديهم دليل على كيفية خفض الحد الأعلى العنيد.

في خوارزمياتهما السابقة، ركزوا على تقييد التناقض الذي يتراكم حتمًا بمرور الوقت. الآن، أضافوا قيودًا إضافية.

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

أراد هو وجيانغ (Jiang) محاولة الكشف عن استقلالية خفية. "بدت وكأنها فكرة مجنونة عندما تبادلناها لأول مرة"، قال. "ولكن عندما تعاملنا معها، ظننا أنها ليست مجنونة كما تبدو."

على مدى الأشهر القليلة التالية، اكتشفوا كيفية تحقيق ذلك. لن تقيس خوارزميتهما الجديدة التناقض الكلي فحسب، بل ستقيس أيضًا "التبعية" — إذا قمت بتغيير سمة واحدة عشوائيًا، فكم سيتغير التناقض بين السمات الأخرى؟ خصص الثنائي أنصاف المتجهات لكل مجموعة، كما فعلت خوارزميات بانسال (Bansal) السابقة. لكن الآن، عندما تعلق الأمر بتغيير تلك الكسور عشوائيًا لجعلها كاملة، صمم بانسال (Bansal) وجيانغ (Jiang) خوارزميتهما بعناية لتقليل التأثيرات المشتركة. "بطريقة ما، على الرغم من أن [السمات] تبدو مرتبطة ظاهريًا"، قال بانسال (Bansal)، "يمكنك التحرك بطريقة لا تزعج بعضها البعض حقًا."

سمح له هذا، هو وجيانغ (Jiang)، بممارسة سيطرة أكبر على كيفية تطور التناقض في كل خطوة. في النهاية، ضمنت خوارزميتهما أنه لـ N متجه، يمكن أن يكون التناقض بحد أقصى log(N) ¼.

إنه أول تحسين على مشكلة كوملوس (Komlós) منذ عقود. "اعتدت أن أعتقد أنه من المرجح أن الحد الذي كان معروفًا من قبل كان هو الحد الصحيح، وأننا كنا بحاجة فقط لإيجاد طريقة لإثبات أنه لا يمكننا القيام بأفضل من ذلك"، قال نيكولوف (Nikolov)، عالم الكمبيوتر بجامعة تورنتو (University of Toronto). "لذلك فوجئت بالتأكيد بأننا تمكنا من تحقيق أفضل بكثير."

"الجذر الرابع للوغاريتم (N) صغير جدًا"، قال دانيال سبيلمان (Daniel Spielman) من جامعة ييل (Yale University). "في حياتك، لن ترى رقمًا يكون فيه الجذر الرابع للوغاريتم (N) أكبر من 5... إنه يقترب كثيرًا من الثابت لكل غرض عملي."

يؤكد تحسين بانسال (Bansal) وجيانغ (Jiang) على الرؤية الأنيقة المدهشة التي تكمن في صميم نظرية التناقض: حتى عندما يكون التوازن المثالي مستحيلًا، فإن الاقتراب منه ممكن، وحتى عملي.

قد يكون هناك المزيد من التقدم في نظرية التناقض قريبًا. والأهم من ذلك، أن خوارزمية بانسال (Bansal) وجيانغ (Jiang) فعالة، وفقًا لريني هيك (Rainie Heck) من معهد ألفريد ريني للرياضيات (Alfréd Rényi Institute of Mathematics) في المجر. تعني هذه الكفاءة أن الباحثين يمكنهم استخدام الخوارزمية للمساعدة في معالجة مشاكل أخرى مفتوحة في نظرية التناقض، بالإضافة إلى مسائل في نظرية التحسين والفيزياء والمالية والمزيد. يدرس هيك (Heck)، على سبيل المثال، كيفية تطبيق نظرية التناقض لتحسين نماذج اللغات الكبيرة وأنظمة التعلم الآلي الأخرى.

وقد يعيد التقدم الأخير تنشيط البحث عن حد كوملوس (Komlós) الثابت "غير المسؤول" أخيرًا. أعرب كل من نيكولوف (Nikolov) وسبيلمان (Spielman) عن ثقتهما المتجددة بأن الفرضية صحيحة. تنشأ الثوابت العالمية غالبًا في مشاكل الرياضيات، وحتى الجذر التربيعي للوغاريتم (N) يظهر بين الحين والآخر. أما الجذر الرابع، فلا يظهر كثيرًا، مما يشير إلى أن هذا لن يكون الحد النهائي. "من النادر جدًا أن يكون ذلك هو الإجابة الصحيحة لأي مشكلة"، قال سبيلمان (Spielman).

يشك بانسال (Bansal) في أن الاستراتيجية الخوارزمية التي استخدمها منذ عام 2010 ستنهي المهمة. "لقد وصلنا إلى طريق مسدود عند الجذر الرابع"، قال. "تجاوز ذلك سيتطلب بالتأكيد شيئًا جديدًا تمامًا."

لكنه منح الباحثين الأمل. "أعتقد حقًا"، قال هيك (Heck)، "أن شخصًا ما سيتمكن من إثبات ذلك."

احصل على أبرز الأخبار الهامة مباشرة إلى صندوق بريدك الإلكتروني

إثبات "مذهل" للانتشار يحل لغزًا عمره عقود حول التحولات الطورية

طالب دراسات عليا يثبت مبدأ عدم اليقين الكمومي للمتعديات الكسرية (Fractals)

لماذا الأنهار رياضية إلى هذا الحد؟

تشرف مجلة كوانتا (Quanta Magazine) على التعليقات لتسهيل محادثة مستنيرة، موضوعية، ومدنية. سيتم رفض التعليقات المسيئة، الفاحشة، الترويجية للذات، المضللة، غير المتماسكة، أو الخارجة عن الموضوع. يعمل المشرفون خلال ساعات العمل العادية (بتوقيت نيويورك) ولا يمكنهم قبول إلا التعليقات المكتوبة باللغة الإنجليزية.

سنرسل إليك تعليمات عبر البريد الإلكتروني لإعادة تعيين كلمة مرورك