مشكلة سهلة السبر تنتج أرقامًا كبيرة جدًا بالنسبة لكوننا | مجلة كوانتا

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

يبدو الأمر بسيطًا بما فيه الكفاية. قال: "يمكنك الذهاب إلى المدرسة الابتدائية وإخبار الأطفال بذلك". كريستوف هاس، عالم الكمبيوتر في جامعة أكسفورد. "سيعتقد الناس أن هذا يجب أن يكون سهلاً".

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

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

في متناول اليد؟

إن مشكلة إمكانية الوصول، إذا تم تجريدها من جوهرها، تتعلق بكائنات رياضية تسمى المتجهات، وهي عبارة عن قوائم مرتبة من الأرقام. تسمى الإدخالات في هذه القوائم بالمكونات، ويسمى عدد المكونات في المتجه بأبعاده. على سبيل المثال، يمكن وصف مخزون الفاكهة الخاص بأليس بواسطة ناقل رباعي الأبعاد (a, b, c, d), تمثل مكوناتها عدد التفاح والموز والشمام والبرتقال الموجودة لديها في أي وقت.

نظام إضافة المتجهات، أو VAS، عبارة عن مجموعة من المتجهات التي تمثل التحولات المحتملة بين الحالات في النظام. بالنسبة إلى أليس، يمثل متجه الانتقال (−1، −1، 1، 0) تبادل تفاحة وموزة مقابل شمام. تتساءل مشكلة إمكانية الوصول إلى VAS عما إذا كان هناك أي مجموعة من التحولات المسموح بها والتي يمكن أن تأخذك من حالة أولية محددة إلى حالة هدف محددة - أو، من الناحية الرياضية، ما إذا كان هناك أي مجموع من متجهات الانتقال التي تحول متجه البداية إلى متجه الهدف. هناك مشكلة واحدة فقط: لا يمكن لأي عنصر من عناصر المتجه الذي يصف حالة النظام أن ينخفض ​​إلى ما دون الصفر.

قال: "هذا قيد طبيعي جدًا لنموذج الواقع". فويتسيك تشيروينسكي، عالم الكمبيوتر في جامعة وارسو. "لا يمكن أن يكون لديك عدد سلبي من التفاح."

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

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

ثانيًا، يحاول الباحثون وضع "حدود عليا" - وهي حدود لمدى صعوبة إمكانية الوصول، حتى في أكثر الأنظمة شيطانية. ويقول هؤلاء: “أصعب الحالات على معين n هي على الأكثر بهذه الصعوبة. لتحديد مدى صعوبة الوصول بدقة في أصعب الأنظمة، يحاول الباحثون دفع الحدود الدنيا إلى الأعلى والحدود العليا إلى الأسفل حتى يلتقيا.

الاشياء من الكوابيس

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

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

ليبتون إذن ثبت يمكنه بناء نظام الحجم n حيث يتضمن أقصر مسار بين حالتين أكثر من انتقالات $latex 2^{2^n}$. وهذا يعني وجود حد أدنى أسي مزدوج مماثل للجهد المطلوب لتحديد إمكانية الوصول في أنظمته. لقد كان اكتشافًا مذهلًا، فالنمو الأسي المزدوج هو مادة كوابيس علماء الكمبيوتر. في الواقع، غالبًا ما يرفض الباحثون حتى النمو الأسي العادي، والذي يتضاءل بالمقارنة: $latex {2^5}= 32$، لكن $latex 2^{2^5}$ يزيد عن 4 مليارات.

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

قال ليبتون: "لقد فكرت بالتأكيد في الأمر بشكل متقطع". "ولكن بعد فترة استسلمت، وبقدر ما أستطيع أن أقول، لم يحرز أحد أي تقدم على مدى ما يقرب من 40 عاما."

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

ولكن هذا ليس ما حدث. وفي عام 2019، اكتشف الباحثون حدًا أدنى أعلى بكثير من حد ليبتون، مما أدى إلى قلب عقود من الحكمة التقليدية. كانت مشكلة إمكانية الوصول إلى خدمات القيمة المضافة (VAS) أكثر تعقيدًا بكثير مما توقعه أي شخص.

برج القوى

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

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

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

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

من الصعب أن تستوعب مدى سرعة خروج القياس عن السيطرة: $latex 2 uparrowuparrow 3$، أو $latex 2^{2^2}$، هو 16، و$latex 2 uparrowuparrow 4$ يزيد قليلاً عن 65,000، و $latex 2 uparrowuparrow 5$ هو رقم يتكون من 20,000 رقم تقريبًا. من المستحيل فعليًا تدوين جميع أرقام $latex 2 uparrowuparrow 6$ — وهي مسؤولية العيش في مثل هذا الكون الصغير.

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

إلى Quinquagintillion وما بعدها 

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

لفهم هذه الوظيفة، خذ النمط المستخدم لتعريف رباعية إلى نهايته القاتمة. العملية التالية في التسلسل، تسمى الخماسية، تمثل رباعية متكررة؛ وتتبعها عملية أخرى (السداسية) للتكفير المتكرر، وهكذا.

دالة أكرمان، التي يُشار إليها بـ $latex A(n)$، هي ما تحصل عليه عندما تتحرك خطوة واحدة لأعلى سلم العمليات هذا مع كل نقطة توقف على خط الأعداد: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$، $latex A(3) = 3^3$، $latex A(4)=4 سهم لأعلى 4=4^{4^{4^4}}$، وهكذا. عدد الأرقام في $latex A(4)$ هو في حد ذاته عدد هائل يساوي تقريبًا 1 كوينكواجينتيليون - هذا هو الاسم الغريب ونادرًا ما نحتاجه للرقم 1 متبوعًا بـ 153 صفرًا. "لا تقلق بشأن أكرمان البالغ من العمر 5"، نصحه خافيير اسبارزا، عالم الكمبيوتر في الجامعة التقنية في ميونيخ.

تركت نتيجة ليروكس وشميتز فجوة كبيرة بين الحدود الدنيا والعليا - يمكن أن يكمن التعقيد الدقيق لمشكلة إمكانية الوصول إلى خدمات القيمة المضافة في أي من طرفي النطاق أو في أي مكان بينهما. لم يكن Czerwiński ينوي ترك هذه الفجوة قائمة. وقال: "لقد واصلنا العمل على هذا لأنه كان من الواضح أنه أكبر شيء قمنا به في حياتنا".

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

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

لم تنتهِ أبدًا

واصل الباحثون دراسة مشكلة إمكانية الوصول إلى خدمات القيمة المضافة (VAS) بعد تحديد مدى تعقيدها الدقيق، حيث لا تزال العديد من المتغيرات للسؤال دون إجابة. على سبيل المثال، لا تميز حدود أكرمان العلوية والسفلية بين الطرق المختلفة للزيادة n, مثل زيادة أبعاد المتجهات أو زيادة عدد التحولات المسموح بها.

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

وقال مازوفيتسكي: "بطريقة ما، هذا أمر محرج بالنسبة لنا".

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

قال زيتشه: "أنا أعتبر هذا جزءًا من مسعى أساسي للغاية لفهم قابلية الحوسبة".

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