كسر الاستعصاء على الحل

كسر الاستعصاء على الحل

يمكن تجاوز استعصاء حل بعض المسائل إذا

اكتفينا عند حسابها بمعرفة ما يحدث في المتوسط.

<F .J. تروب> ـ <H. ڤوزنياكوڤسكي>

 

على الرغم من أنه يجب اعتبار الرياضياتيين والعلميين بين أكثر العقلانيين من الناس، فإنهم كثيرا ما يقعون ضحية لما يسمى لعنة البعد curse of dimension، التي تنصب على كثير من الناس بشكل من الأشكال. فعلى سبيل المثال، من الصعوبة بمكان توصل عائلة إلى قرار بشأن ما إذا كان من الأفضل تسديد قرض عقارها خلال 15 سنة أو 30 سنة، ذلك أن الخيار بينهما يتوقف على العلاقة بين النفقات الشهرية والدخل والضريبة المستقبلية ومعدلات الفائدة وأمور متقلبة أخرى. أما في العلم، فإن المسائل لا تكون مفهومة إلا من قبل فئات قليلة من الناس، كما أن التصدي لها غالبا ما يتسم بالصعوبة والتعقيد. ففي التخطيط المدعوم باستخدام الحاسوب لإنتاج مستحضر صيدلاني، مثلا، قد نحتاج إلى معرفة مدى ارتباط عقار مقترح بمستقبِل receptor  بيولوجي. وبافتراض عدد نموذجي قدره 8000 ذرة في العقار والمستقبل البيولوجي والمذيب solvent، فإن الحسابات عندئذ تتضمن 000 24 متغير بسبب المتغيرات المكانية (الإحداثيات) اللازمة لتحديد موضع كل ذرة. ويمكن القول ببساطة بأنه كلما ازداد عدد المتغيرات، أي الأبعاد، في مسألة ما، ازدادت صعوبة حلها. وفي كثير من المسائل، فإن الصعوبة تتزايد أُُسِّيا exponentially مع عدد المتغيرات.

 

مسألة قد تكون عصية الحل

 

ويمكن أن تصعِّد لعنة البعد من مستوى الصعوبة إلى درجة تغدو فيها المسألة عصية الحل. وعلى الرغم من وجود حواسيب تحت تصرف العلميين، فإن المسائل قد تتضمن عددا كبيرا من المتغيرات إلى حد يجعل من أي زيادة مستقبلية في السرعة الحاسوبية عاجزة عن حل هذه المسائل خلال فترة معقولة من الزمن.

 

تُرى، هل يمكن جعل المسائل العصية الحل مطواعة للحل ـ أي ممكنة الحل خلال مدة مقبولة من الزمن الحاسوبي؟ أحيانا تكون الإجابة لحسن الحظ بنعم. ولكن علينا في هذه الحالة أن نقوم بذلك دون ضمان بأن حساباتنا لن تخلو من أخطاء صغيرة. وفي حال وقوع أخطاء صغيرة معظم الوقت (وليس دائما)، فإن بعض أنواع المسائل التي تحوي عدة متغيرات تغدو مطواعة للحل. وقد برهن أحدنا (ڤوزنياكوڤسكي) أن مثل هذا الأمر ينجح في فئتين على الأقل من المسائل الرياضياتية التي تبرز على نحو متكرر في الأعمال العلمية والهندسية. أولى هاتين الفئتين هي مسائل المكاملة integration، وتمثل المكاملة جزءا أساسيا في الحسبان (حساب التفاضل والتكامل) calculus. أما الأخرى فهي إعادة إنشاء السطوح surface reconstruction، حيث تستعمل عينات من المعلومات عن جسم لإعادة إنشائه، وهي تقنية تكوِّن أساس التصوير الطبي.

 

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

 

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

 

إن التعقّد المؤسس على المعلومات يركز على الصعوبة الحسابية لما يسمى بالمسائل المتصلة (المستمرة) continuous. وحساب حركة الكواكب السيارة هو مثال على ذلك. فهذه الحركة محكومة بنظام من المعادلات التفاضلية العادية ـ أي معادلات لتحديد مواضع هذه الكواكب كدوال functions للزمن. ولما كان من الممكن  أن يأخذ الزمن أي قيمة حقيقية، فإنه يقال إن النموذج الرياضياتي متصل. والمسائل المتصلة تختلف عن المسائل المتقطعة discrete  كالمعادلات الفَرْقيّةdifference equations التي يأخذ فيها الزمن قيما صحيحة فقط. وتَرِد المعادلات الفرقية في بعض التحليلات، كأن نبحث عن العدد الذي يمكن التنبؤ به من الحيوانات المفترسة في دراسة مجمعات من الحيوانات المفترسة والفرائس، أو أن نبحث عن مستويات التلوث المتوقعة في بحيرة.

 

بيد أن السائد في الممارسات اليومية في مجالي العلم والهندسة هو الصياغات الرياضياتية المتصلة. فهي تتضمن حشدا من المسائل كالمعادلات التفاضلية العادية والجزئية والمعادلات التكاملية والأمْثلة optimization الخطية وغير الخطية والمكاملة وإعادة إنشاء السطوح. وهذه الصياغات تتضمن غالبا عددا كبيرا من المتغيرات. وعلى سبيل المثال، فإن الحسابات في الكيمياء وفي تصميم المستحضرات الصيدلانية وفي علم المعادن غالبا ما تستلزم حسابات للمواضع في الفضاء وللزخوم (كميات الحركة) momenta لآلاف الجسيمات.

 

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

 

وبغية طرح مشكلة الاستعصاء على الحل بصورة أدق ومناقشة معالجاتها الممكنة، فإننا سننظر في مثال حساب المساحة تحت منحن. وتشبه هذه العملية حساب السطح الرأسي الذي يشغله صف من الكتب الموضوعة على رف. وعلى نحو أوضح، فإننا سنحسب المساحة المحصورة بين طرفي الصف. ومن دون الحد من عمومية المسألة، يمكننا أن نفترض أن طرفي الصف يقعان عند 0 و1. وتسمى هذه العملية في الرياضيات حساب التكامل المحدد definite integral. (وعلى نحو أدق، فإن المساحة مشغولة بعدد غير منته من الكتب ثخانة كل منها لامتناهية في الصغر.) إن المُدْخَلَ input الرياضياتي لهذه المسألة يسمى الدالة المكاملة integrand، وهي دالة تصف الشكل الجانبي للكتب المصفوفة على الرف.

 

حل لمسألة مستعصية

 

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

 

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

 

تشير نقاط المعاينة sampling إلى الأمكنة التي تُحسَب عندها قيم الدوال في وضع الحالة المتوسطة ووضع العشوأة randomized. وقد رسمت النقاط في حالة بعدين بغية الإيضاح. ويمكن فصل النقاط بعضها عن بعض بمجالات منتظمة، كأن تكون نقاطا شبكية (a)، أو نقاطا موزعة عشوائيا (b). وهنالك نمطان آخران هما نقاط هامرسلي (c) والنقاط المتصالبة الزائدية (d )، يمثلان المواضع الأمثلية optimal في وضع الحالة المتوسطة.

 

وحتى هذا الهدف لا يمكن بلوغه دون مزيد من القيود. فمعرفة الدالة المكاملة في النقطتين 0.2 و0.5، مثلا، لا ينبئنا بشيء عن شكل المنحني بين هاتين النقطتين. فمن الممكن أن يتخذ المنحني أي شكل بينهما، ومن ثم فإنه يمكن أن يحتضن أي مساحة. ولضمان خطأ لا تتجاوز قيمته ε، فإننا بحاجة إلى معرفة شاملة للدالة المكاملة. وعلى سبيل المثال، فقد نحتاج إلى افتراض أن ميل منحني الدالة يقل دوما عن 45 درجة ـ أو افتراض أنه لا يسمح إلا للكتب الورقية الغلاف بأن توضع على الرف.

 

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

 

تطوير المعالجة العشوائية

<M .S. أولام> ، 1984 – 1909 في الأربعينات من هذا القرن أدرك الفيزيائيون العاملون في مشروع مانهاتن في مختبر لوس ألاموس الوطني أن بعض المسائل التي كانوا يسعون إلى إيجاد حل لها، كحركة النيوترونات خلال المواد، تقع خارج نطاق الحسابات التعيينية. لذا اتجهوا إلى استخدام طريقة مونت كارلو التي ابتدعها <C .N. متروبوليس> و<M .S. أولام>. وتكمن قوة هذه الطريقة في أن الخطأ مستقل عن عدد المتغيرات الواردة في المسألة. ومن ثم، فإذا كانت الطريقة قابلة للتطبيق، فإنها ستخلصنا من «لعنة البعد». وتتطلب طريقة مونت كارلو التقليدية في المكاملة المتعددة المتغيرات عددا من التقديرات في نقاط عشوائية من مرتبة  1/ε2   على الأكثر، حيث ε  هو عتبة الخطأ. وهذا يعني أنه إذا كانت الدالة المكاملة مقدرة في n من النقاط العشوائية، فإن الخطأ المتوقع للعشوأة يكون من مرتبة تبلغ /1    على الأكثر. ومنذ تأسيسها أثبتت هذه الطريقة والتحسينات التي أدخلت عليها، أنها مفيدة في حساب مجموعة متنوعة من الظواهر الطبيعية بدءا من حجم الوابل الكوني cosmicshower  إلى نفوذ سائل عبر جسم صلب. وفي حال المكاملة المتعددة المتغيرات، فإن طريقة مونت كارلو التقليدية لا تكون أمثلية إلا حينما يكون وسيط الملاسة r للدوال المكاملة صفرا. وفي عام 19599 بدأ عالم الرياضيات الروسي <S .N. بخڤالوف> بإجراء بحث ريادي في التعقد الحسابي computational complexity للمكاملة المتعددة المتغيرات في الحالة المعشوأة وابتكر بديلا لطريقة مونت كارلو. وفي عام 1988 طور <Ε. نوڤاك> من جامعة إيرلانگن ـ نورنبرگ عَمَل بخڤالوف وأثبت أن التعقد الحسابي في الحالة المعشوأة هو من مرتبة (1/ε)s، حيث s=2/(1 + 2r/d). علما بأن  s≤ 2و> 0  وإذا كان وسيط الملاسة مساويا للصفر فإنs = 2 ، وعندئذ تكون طريقة مونت كارلو التقليدية أمثلية. ومن ناحية أخرى، إذا كان r موجبا، فإن طريقة مونت كارلو التقليدية تكف عن كونها أمثلية، وعندئذ يمكن استخدام طريقة بخڤالوف بدلا منها.

 

وهكذا، فإنه بمقدورنا الآن تقديم المفهوم الأساسي للتعقّد الحسابيcomputational complexity. وفي هذا الصدد، فإن ما نرغب فيه هو إيجاد الصعوبة الجوهرية في حل مسألة المكاملة. لنفترض أن لكلٍّ من تحديد قيم الدالة المكاملة واستعمال عمليات ضمّية combinatory operations، مثل الجمع والضرب والمقارنة، تكلفة مفروضة. وقد تكون التكلفة ببساطة هي المدة الزمنية التي يتطلبها حاسوب لإنجاز العملية. عندئذ يمكن تعريف التعقد الحسابي لمسألة المكاملة هذه بأنه التكلفة الأصغرية لضمان كون الجواب المحسوب واقعا ضمن عتبة خطأ ε للقيمة الحقيقية. وتكون عمليات المعلومات الأمثلية optimal  وخوارزمي  العمليات الضمية الأمثلي هي تلك التي تخفض التكلفة إلى حدها الأدنى.

 

وقد بينت المبرهنات أن التعقد الحسابي لمسألة المكاملة هذه هو من مرتبة تساوي مقلوب عتبة الخطأ(1/ε) . وبعبارة أخرى، فمن الممكن اختيار مجموعة من عمليات المعلومات وخوارزمي ضمي بحيث يقرّب الحل بتكلفة تبلغ (1/ε)تقريبا. ومن المستحيل أن نفعل أفضل من هذا. ففي حالة متغير واحد، أي بعد واحد، تكون المسألة بسيطة إلى حد ما، إذ إن التعقد الحسابي يتناسب عكسيا مع الدقة المطلوبة.

 

أما إذا وجدت أبعاد أكثر لمسألة المكاملة هذه، فإن التعقد الحسابي عند ذلك يتزايد أسيا مع عدد المتغيرات. فإذا كان d عدد المتغيرات، فإن التعقد هو من مرتبة (1/ε)^d  ـ أي إنه مقلوب عتبة الخطأ مرفوعا إلى قوة تساوي عدد المتغيرات. ومن ثم فإذا رغبنا في دقة قدرها 0.000000011 لدى حساب تكامل فيه ثلاثة متغيرات، فإن التعقد الحسابي يساوي تقريبا 10²⁴. وبكلمات أخرى، فإنه يلزم ترليون ترليون قيمة للدالة المكاملة للارتقاء إلى هذا المستوى من الدقة. وحتى لو افترضنا جدلا وجود حاسوب تتابعي sequential باستطاعته إنجاز 100 بلايين تقدير للدالة في الثانية، فإن المهمة ستستغرق 1000 ترليون ثانية، أي أكثر من ثلاثة ملايين سنة. أما الحاسوب الذي يحوي مليون معالج processor، فإنه يحتاج مع ذلك إلى 100 مليون ثانية، أي نحو ثلاث سنوات.

 

ولدراسة المسائل المتعددة المتغيرات multivariate على نحو أعم، فإنه يتعين علينا إدخال وسيط parameter إضافي يسمى r. ويمثل هذا الوسيط ملاسةsmoothness  المدخلات الرياضياتية. ونعني بالملاسة أن المدخلات تتكون من دوال لا تعاني أي تغيرات مفاجئة أو درامية. (يقول الرياضياتيون إن جميع المشتقات الجزئية للدالة حتى المرتبة r محدودة.⁽¹⁾) ويأخذ الوسيط قيما صحيحة غير سالبة، والقيم المتزايدة له تشير إلى مزيد من الملاسة. ومن ثم تمثل r = 00 أقل قدر من الملاسة (وهذا يعني تقنيا أن الدوال المكاملة تكون متصلة فقط ـ وتكون منحنياتها مسننة إلى حد ما، لكنها تبقى مترابطة connεctεd كمنحن وحيد).

 

وللعديد من المسائل تعقّد حسابي من مرتبة (1/ε)^d/r. ويرى أولئك الذين لديهم ميل أشد إلى النواحي التقنية أن المكاملة المتعددة المتغيرات وإعادة إنشاء السطوح والمعادلات التفاضلية الجزئية والمعادلات التكاملية والأمْثلة غير الخطية، لها جميعها هذا التعقد الحسابي.

 

تعقد الحالة المتوسطة

ذكرنا في متن المقالة أن تعقد الحالة المتوسطة للمكاملة المتعددة المتغيرات هو من مرتبة مقلوب عتبة الخطأ (أي إنه: (1/ε)، وهو في حالة إعادة إنشاء السطوح مربع هذا المقلوب (أي: 2 1/ε). وبغية التبسيط، فقد تجاهلنا بعض العوامل الضربية التي تعتمد على  ε وd. وسنقدم فيما يلي عبارات أدق: إن التعقيد الحسابي المتوسط، ونرمز له ب:compavg(ε , d; INT) ، للمكاملة المتعددة المتغيرات يحقق المتباينتين التاليتين:

 

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

 

ومن وجهة النظر الرياضياتية، فإن نتائج التعقد الحسابي التي شرحناها تسري على ما يسمى الوضع التعييني في أسوأ الحالات worst-casedeterministic setting. وعبارة «في أسوأ الحالات» تأتي من حقيقة أن التقريب يوفر ضمانا لوقوع الخطأ دوما في حدود ε. وبعبارة أخرى، ففي حالة المكاملة المتعددة المتغيرات، يمكن ضمان تقريب ضمن عتبة الخطأ من أجل كل دالة مكاملة لها ملاسة مفروضة. أما كلمة «التعييني» فتنشأ عن حقيقة أن الدالة المكاملة يجري حساب قيمتها عند نقاط معينة (لاعشوائية).

 

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

 

إن إحدى الطرق الممكنة لوضع حد لعدم قابلية الحل أو استعصائه هي العَشْوأة randomization. ولشرح كيف تعمل العشوأة، فإننا نستخدم المكاملة المتعددة المتغيرات ثانيةً. وبدلا من انتقاء النقاط بصورة تعيينية deterministic، أو حتى أمثلية optimal، فإننا نسمح (بمعنى غير رسمي) لقطعة نقود نقذفها في الهواء باتخاذ القرار نيابة عنا. وقد يكون إجراء استفتاء تشبيها غير دقيق على ذلك. فعوضا عن سؤال كل مُستفتى مسجل، يقوم مستطلِع للرأي بأخذ عينة عشوائية صغيرة ليقرر الفائز المحتمل.

 

وتشير المبرهنات إلى أنه لدى الاختيار العشوائي للنقاط، فإن التعقد الحسابي هو على الأكثر من مرتبة مقلوب مربع عتبة الخطأا ²ا1/ε . وهكذا فإن المسألة تكون مطواعة دائما، حتى وإن كان وسيط الملاسة مساويا للصفر.

 

لقد كانت الآلية المتميزة للمعالجة المُعَشوأة randomized هي طريقة مونت كارلو التي اقترح فكرتها <C .N. متروبوليس> و<M .S. أولام> في الأربعينات من هذا القرن. وفي طريقة مونت كارلو التقليدية يجري تقييم الدالة المكاملة في نقاط عشوائية موزعة بانتظام. وعندئذ يُتَّخذ الوسط الحسابي لقيم الدوال هذه تقريبا approximation  للحل.

 

ومن المثير للدهشة في مسائل المكاملة المتعددة المتغيرات أن العشوأة من هذا النوع تجعل التعقد الحسابي مستقلا عن عدد الأبعاد. والمسائل غير القابلة للحل أو العصية الحل لدى حسابها من أفضل النقاط التعيينية الممكنة، تصير مطواعة لدى معالجتها عشوائيا. (لكنه إذا كان r موجبا، فلن تكون طريقة مونت كارلو التقليدية الطريقة الأمثلية [انظر ما هو مؤطر في الصفحة 122].

 

التعقّد الحسابي للمسائل المتقطعة

تناقِش هذه المقالة الاستعصاء على الحل وكسره في المكاملة المتعددة المتغيرات وفي إعادة إنشاء السطوح. وهاتان الحالتان توفران مثالين على المسائل المتصلة. لكن ما المعروف عن التعقد الحسابي للمسائل المتقطعة دون المتصلة؟ إن مسألة مندوب المبيعات المتجول الشهيرة هي مثال على مسألة متقطعة يطلب إليه فيها زيارة مدن مختلفة بقطع أقصر مسافة ممكنة. وتكون مسألة متقطعة عصية الحل إذا كان تعقدها الحسابي متزايدا أسيا مع عدد مُدخلاتها. وقد جرى تخمين استعصاء حل كثير من المسائل المتقطعة عندما تكون في «الوضع التعييني في أسوأ الحالات»، إلا أن هذه التخمينات لم تبرهن بعد. والمعلوم هو أنه يوجد لمئات من المسائل المتقطعة تعقد حسابي واحد، بمعنى أنها جميعا عصية الحل أو أنها جميعا مطواعة للحل. والاعتقاد السائد بين الخبراء هو أنها جميعا عصية الحل. ولأسباب تقنية، فإنه يقال إن هذه المسائل تامة من النمطNP NP-complete. وإحدى المسائل الشهيرة التي لم يفصل فيها بعد في نظرية التعقد الحسابي المتقطع هي تحديد ما إذا كانت المسائل التامة من النمط NP عصية الحل حقا. [انظر: “TuringMachines,” by John Ε. Hopcroft; Scientific American, May 1984].

 

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

 

إن العشوأة تجعل المكاملة المتعددة المتغيرات ومسائل مهمة كثيرة أخرى ممكنة حسابيا. بيد أنها ليست العلاج العام لجميع المسائل، وذلك يعود إلى فشلها كليا في بعض أنواع المسائل. وعلى سبيل المثال، فقد بيَّن <W .G. ڤاسيلكوڤسكي> (من جامعة كنتاكي عام 1987) أن العشوأة لا تكسر استعصاء حل مسائل إعادة إنشاء السطوح. تُرى، هل هناك طريقة ناجعة تصلح لأن تطبق على فئة واسعة من مسائل الرياضيات؟

 

نعم، هذه الطريقة موجودة فعلا، إنها وضع الحالة المتوسطة average-casesetting، حيث نسعى إلى كسر عدم قابلية الحل أو استعصائه بأن نستعيض عن ضمان الوضع التعييني في أسوأ الحالات بضمان أضعف: وهو أن يكون الخطأ المتوقع مساويا ε على الأكثر. ويفرض وضع الحالة المتوسطة قيودا على نوع المدخلات الرياضياتية. ويجري اختيار هذه القيود لتمثل ما يحدث معظم الوقت. وتقنيا، فإن القيود تتحدد بالتوزيعات الاحتمالية probabilitydistributions، وهذه التوزيعات تحدد احتمال حدوث مدخلات معينة. وأكثر التوزيعات استعمالا في هذا الشأن هي قياسات گاوس Gaussian measures، وبوجه خاص، قياسات وينر Wiener.

 

وعلى الرغم من أنه كان معلوما منذ الستينات أن مسألة المكاملة المتعددة المتغيرات مطواعة للحل في المتوسط، فإن البرهان كان غير بنّاء، أي إنه لم يحدد النقاط الأمثلية لحساب الدالة المكاملة والخوارزمي الضمي الأمثلي والتعقد الحسابي المتوسط. هذا وقد جانب التوفيق محاولات تطبيق أفكار مستقاة من مجالات أخرى من الحساب computation  بغية تحديد هذه المجاهيل. وعلى سبيل المثال، فإن حساب قيمة الدالة المكاملة في نقاط تفصلها مسافات منتظمة، كأن تكون هذه النقاط موزعة على شبكة، غالبا ما يستخدم في الحساب. إلا أن المبرهنات بينت أنها اختيارات غير موفقة لوضع الحالة المتوسطة. إن أحد البراهين أورده <D .N. إلڤسْكر> (من جامعة كاليفورنيا في لوس أنجلوس) عام 1975. وفي عام 1990 جرى تعميم هذا البرهان من قبل ڤاسيلكوڤسكي و<A. پاپاجورجيو> الذي كان يدرس حينذاك في جامعة كولومبيا للحصول على الدكتوراه.

 

وقد أُنجز الحل عام 1991 حين توصل ڤوزنياكوڤسكي إلى إنشائه. وكما يحدث أحيانا في العلم، فقد كان لنتيجة من نظرية الأعداد، وهي فرع من الرياضيات بعيد كل البعد عن نظرية تعقد الحالة المتوسطة، دور حاسم. وقد أُنجز قسم رئيسي من الحل استنادا إلى بحث في نظرية الأعداد قام به <F .K. روث> من الإمبريال كولج في لندن، وهو أحد الحاصلين على ميدالية فيلدز عام 1958. كما قُدم قسم آخر من الحل في بحث حديث قام به ڤاسيلكوڤسكي.

 

سنشرح هذه النتيجة على نحو أدق. أولا، نضع وسيط الملاسة في الصفر ـ أي إننا نعالج مسألة غير قابلة للحل في الوضع التعييني في أسوأ الحالات. بعد ذلك نفترض أن الدوال المكاملة موزعة حسب قياس وينر. وإذا تجاهلنا ـ بغية التبسيط ـ عوامل ضربية معينة، فقد تم البرهان على أن التعقد الحسابي المتوسط متناسب عكسيا مع عتبة الخطأ (من مرتبة 1/ε) [انظر ما هو مؤطر في الصفحة 13]. وفي حالة الأخطاء الصغيرة، فإن النتيجة تمثل تحسينا رئيسيا لطريقة مونت كارلو التقليدية حيث تتناسب التكلفة عكسيا مع مربع عتبة الخطأ (1/ε²).

 

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

 

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

 

وفي وضع الحالة المتوسطة، فإنه يجب أن تُختار نقاط التقييم الأمثلية theoptimal evaluation points بطريقة تعيينية. وأفضل النقاط هي نقاط هامَرْسليHammersley أو النقاط المتصالبة الزائدية hyperbolic-cross points [انظر الشكل في الصفحتين 12 و13]. وتوفر النقاط التعيينية هذه اختيارا للعينات أفضل مما توفره النقاط المختارة عشوائيا أو النقاط التي تفصل بينها مسافات منتظمة. وهي تجعل ما يستحيل حله مطواعا للحل في المتوسط.

 

تُرى، هل إعادة إنشاء السطوح مسألة مطواعة للحل أيضا في المتوسط؟ إن هذا التساؤل مهم جدا لأن العشوأة، كما ذُكر سابقا، لا تقدم لنا هنا أي عون. فضمن الافتراضات نفسها التي استعملناها في المكاملة، نجد أن التعقّد الحسابي المتوسط هو من مرتبة 1/ε². ومن ثم فإن إعادة إنشاء السطوح تصبح مسألة مطواعة للحل في المتوسط. وكما كانت الحال في المكاملة، فإن النقاط المتصالبة الزائدية أمثلية.

 

سنختبر الآن ما إذا كانت الحالة المتوسطة هي بديلا عمليا. يقوم حاليا طالب يحضر للدكتوراه في جامعة كولومبيا بتطوير برامجيات software لمقارنة التقنيات التعيينية بطرائق مونت كارلو في المكاملة. وتوحي بعض النتائج الأولية المستخلصة من اختبار مسائل مالية معينة بتفوّق الطرائق التعيينية في التطبيقات العملية.

 

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

 

وقد كشف ڤوزنياكوڤسكي النقاب عن حل وهو: التخلص من هذا العامل. وعلى وجه التحديد، فإننا نقول عن مسألة إنها مطواعة جدا للحل إذا كان عدد تقييمات الدالة اللازم لحلها مستقلا تماما عن عدد المتغيرات. وفيما عدا ذلك، فإنه يعتمد فقط على قوة للعدد 1/ε. وتبدو هذه الإمكانية بعيدة المنال، بيد أنه تم في عام 1992 إثبات أن المكاملة المتعددة المتغيرات وإعادة إنشاء السطوح كلتيهما مطواعتان جدا للحل في المتوسط.

 

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

 

لقد قادت البحوث في مجال التعقد المؤسَّس على المعلومات أحدنا (تروب) لأن يخمن بأنه قد يكون من الممكن إثبات أن مسائل علمية معينة لا يمكن الإجابة عنها. والطريقة المقترحة للتوصل إلى هذا التخمين هي البرهان على أن مصادر الحساب (الزمن والذاكرة والطاقة) ليست متوافرة في الكون كي تجيب عن مثل هذه الأسئلة.

 

إن أحد الإنجازات المهمة في الرياضيات على مدى الستين سنة الأخيرة يتجلى في الفكرة القائلة بأن المسائل الرياضياتية قد تكون غير قابلة للحسم أو غير قابلة للحساب أو عصية الحل. وقد أثبت <K. كودل> أولى هذه النتائج عندما بين أنه توجد في بعض الأنظمة الرياضياتية الغنية بقدر كاف، كعلم الحساب arithmetic مثلا، مبرهنات لا يمكن إثباتها.

 

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

 

لماذا تشير نتائج استعصاء الحل إلى أن بعض الأسئلة العلمية قد لا يمكن توفير إجابة لها؟ لنُعِدْ ذكر النتائج التي توصلنا إليها. ففي الوضع التعييني في أسوأ الحالات، يتزايد التعقد الحسابي في كثير من المسائل المتصلة أسّيّا مع عدد الأبعاد. كذلك، فإنه يخمَّن بأن التعقد الحسابي للعديد من المسائل المتقطعة يتزايد أسيا مع عدد المدخلات [انظر ما هو مؤطر في الصفحة 106]. فضلا عن ذلك، فإنه على الرغم من كون بعض المسائل مطواعة للحل في الوضع المعشوأ randomized أو وضع الحالة المتوسطة، فإنه جرى البرهان على أن مسائل أخرى تبقى عصية الحل. ومثل هذه المسائل قد تنتمي إلى مسائل معينة تعالجها الحواسيب الفائقة supercomputers، أو إلى مسائل تتعلق بأسس الفيزياء. ومع كل ذلك، فإنها تحوي عددا كبيرا من المتغيرات أو الجسيمات. بل إن الأمر أسوأ من ذلك، إذ إن كثيرا من مسائل الفيزياء تتطلب حلولا لنوع من التكاملات تسمى التكاملات الممرية path integrals  التي لها عدد غير منته من الأبعاد. وتستدعي حلول التكاملات الممرية تقريبات عدد أبعادها كبير. وهكذا فإن نتائج استعصاء الحل ومُخَمَّناته conjectures، مثبطة للهمم قطعا، لأنها توحي بأن كثيرا من المسائل التي تحوي عددا كبيرا من المتغيرات أو الأشياء قد تكون مستحيلة الحل.

 

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

 

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

 

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

 

 المؤلفان

Josεph F. Traub – Hεnryk Wozniakowski

 

اشتركا في إجراء عدد من البحوث منذ عام 1973. يشغل تروب حاليا أستاذ كرسي إدوين هوارد آرمسترونگ لعلم الحاسوب في جامعة كولومبيا، ترأس قسم علم الحاسوب في جامعة كارنيگي ميلون، كما كان المؤسس الرئيسي لهيئة علم الحاسوب والاتصالات عن بعد التابعة للأكاديمية الوطنية للعلوم. وفي عام 1959 بدأ بحوثه الريادية فيما يسمى اليوم التعقد المؤسس على المعلومات، وتبوأ عدة مناصب تكريما له بما فيها اختياره رئيسا للأكاديمية الوطنية للهندسة. وهو يقر بالجميل للباحثين في معهد سانتافي للمحادثات المهمة العديدة التي أجراها معهم حول حدود المعرفة العلمية.أما ڤوزنياكوڤسكي فهو يشغل منصبين ثابتين في جامعتي وارسو وكولومبيا. وقد ترأس قسم الرياضيات وعلم الحاسوب والميكانيك في جامعة وارسو وكان رئيس حزب التضامن هناك. ولقد حصل عام 1988 على جائزة مازر Mazur Prize من الجمعية الرياضياتية البولونية. ويتوجه المؤلفان بالشكر الجزيل إلى مؤسسة العلوم الوطنية وإلى مكتب القوى الجوية للبحوث العلمية (في الولايات المتحدة) لتقديمهما الدعم لهما.

مراجع للاستزادة 

INFORMATION-BASED COMPLEXITY. E. W. Packel and J. F. Traub in Nature, Vol. 328, No. 6125, pages 29-33; July 2, 1987.

INFORMA’FION-BASED COMPLEXITY. J. F. Traub, G. W. Wasilkowski and H. Wozniakowski. Academic Press, 1988.

AVERAGE CASE COMPLEXITY OF MULTIVARIATE INTEGRATION. H. Wozniakowski in Bulletin of the American Mathematical Society, Vol. 24, No. 1, pages 185-194; January 1991.

THE COMPUTATIONAL COMPLEXITY OF DIFFERENTIAL AND INTEGRAL EQUATIONS: AN INFORMATION-BASED APPROACH. Arthur G. Werschulz. Oxford University Press, 1991.

THEORY AND APPLICATIONS OF INFORMATION-BASED COMPLEXITY. J. F. Trallb and H. Wozniakowski in 1990 Lectures in Complex Systems, Santa Fe Institute. Edited by Lynn Nadel and Daniel L. Stein. Addison-Wesley, 1991.

WHAT IS SCIENTIFICALLY KNOWABLE? J. F. Traub in Carnegie Mellon University Computer Science: A 25th Anniversary Commemorative. Edited by Richard F. Rashid. Addison-Wesley, 1991.

Scientific American, January 1994

(1) في نظرية الدوال الحقيقية لعدة متغيرات تسمى هذه الدالة دالة قابلة للمفاضلة (فضولة) r مرة r – timεs diffεrεntiablε function، ويقال عنها أحيانا إنها دالة cr-1. (التحرير)