التعقيد والحساب الحقيقي

كتاب "التعقيد والحساب الحقيقي" يتناول نظرية التعقيد الحسابي للحساب الحقيقي . يدرس الكتاب الخوارزميات التي تكون مدخلاتها ومخرجاتها أعدادًا حقيقية ، مستخدمًا آلة بلوم-شوب-سميل كنموذج للحساب . على سبيل المثال، تستطيع هذه النظرية الإجابة على سؤال طرحه روجر بنروز عام 1991 في كتابه "عقل الإمبراطور الجديد" : "هل مجموعة ماندلبروت قابلة للحساب؟" ^{[ 1 ]}

ألّف الكتاب كلٌّ من لينور بلوم ، وفيليبي كوكر ، ومايكل شوب ، وستيفن سميل ، وكتب مقدمته ريتشارد إم. كارب ، ونُشر بواسطة دار نشر سبرينغر-فيرلاغ عام 1998 ( doi:10.1007/978-1-4612-0701-6 ، ISBN) . 0-387-98281-7). ^{[ 2 ]}

يلاحظ ستيفن فافاسيس أن هذا الكتاب يسدّ ثغرةً كبيرةً في الأدبيات: فعلى الرغم من أن علماء الحاسوب النظريين العاملين على الخوارزميات المنفصلة كانوا يدرسون نماذج الحوسبة وتأثيراتها على تعقيد الخوارزميات منذ سبعينيات القرن الماضي، إلا أن الباحثين في مجال الخوارزميات العددية قد فشلوا في الغالب في تحديد نموذج الحوسبة الخاص بهم، مما جعل نتائجهم على أساسٍ هشّ. وإلى جانب هدف جعل هذا الجانب من الموضوع أكثر رسوخًا، يهدف الكتاب أيضًا إلى عرض نتائج جديدة في نظرية تعقيد حساب الأعداد الحقيقية، وجمع النتائج المعروفة سابقًا في هذه النظرية. ^{[ 3 ]}

تتضمن مقدمة الكتاب إعادة نشر ورقة بحثية بعنوان "التعقيد والحوسبة الحقيقية: بيان"، سبق أن نشرها المؤلفون أنفسهم. يشرح هذا البيان لماذا تُعدّ النماذج المنفصلة الكلاسيكية للحوسبة، مثل آلة تورينج، غير كافية لدراسة المسائل العددية في مجالات كالحوسبة العلمية والهندسة الحسابية ، مما يحفز النموذج الأحدث الذي يتناوله الكتاب. وبناءً على ذلك، ينقسم الكتاب إلى ثلاثة أجزاء. ^{[ 2 ]}

يُقدّم الجزء الأول من الكتاب نماذج حسابية لأي حلقة ، بتكلفة وحدة واحدة لكل عملية على الحلقة. ويُوفّر نظائر لنظرية الاستدعاء الذاتي ومسألة P مقابل NP في كل حالة، ويُثبت وجود مسائل NP-كاملة بشكل مماثل لإثبات نظرية كوك-ليفين في النموذج الكلاسيكي، والتي يُمكن اعتبارها حالة خاصة من هذه النظرية للحساب بتردد 2. وتُدرس حلقة الأعداد الصحيحة كمثال خاص، وكذلك الحقول المغلقة جبريًا ذات الخاصية الصفرية، والتي يُبيّن من وجهة نظر اكتمال NP ضمن نماذجها الحسابية أنها جميعًا مُكافئة للأعداد المركبة . ^{[ 2 ]} ( يشير إريك باخ إلى أن هذا التكافؤ يُمكن اعتباره شكلاً من أشكال مبدأ ليفشيتز ). ^{[ 4 ]}

يركز الجزء الثاني على خوارزميات التقريب العددي، واستخدام طريقة نيوتن لهذه الخوارزميات، ونظرية ألفا للمؤلف ستيفن سميل للتحقق العددي من دقة نتائج هذه الحسابات. وتشمل المواضيع الأخرى التي يتناولها هذا القسم إيجاد جذور كثيرات الحدود ونقاط تقاطع المنحنيات الجبرية ، ورقم حالة أنظمة المعادلات، والتعقيد الزمني للبرمجة الخطية ذات المعاملات النسبية . ^{[ 2 ]}

يُقدّم الجزء الثالث نظائر لنظرية التعقيد البنيوي ونظرية التعقيد الوصفي لحساب الأعداد الحقيقية، بما في ذلك العديد من تصنيفات فئات التعقيد التي يُمكن إثباتها في هذه النظرية، على الرغم من أن التصنيفات المماثلة في نظرية التعقيد الكلاسيكية لا تزال غير مُثبتة. وتتمثل إحدى الأدوات الرئيسية في هذا المجال في استخدام عدد المكونات المتصلة لمجموعة شبه جبرية لتوفير حد أدنى للتعقيد الزمني لمسألة حسابية مُرتبطة بها. ^{[ 2 ]}

يستهدف الكتاب مستوى طالب الدراسات العليا أو الباحث في هذه المواضيع، ^{[ 2 ] [ 3 ]} ويفترض في بعض المواضع معرفة مسبقة بنظرية التعقيد الحسابي الكلاسيكية، والهندسة التفاضلية ، والطوبولوجيا ، والأنظمة الديناميكية . ^{[ 3 ] [ 4 ]}

يكتب المراجع كلاوس مير أن الكتاب "مكتوب بشكل جيد للغاية"، و"مثالي للاستخدام على مستوى الدراسات العليا"، ويمثل بشكل جيد كلاً من أحدث ما توصل إليه العلم في هذا المجال والروابط القوية التي يمكن إقامتها بين مجالات متنوعة مثل نظرية الأعداد الجبرية ، والهندسة الجبرية ، والمنطق الرياضي ، والتحليل العددي . ^{[ 2 ]}

في نقدٍ طفيف، موجهٍ بالدرجة الأولى إلى نموذج بلوم-شوب-سميل أكثر من الكتاب نفسه، يلاحظ ستيفن فافاسيس أن (على عكس آلات تورينج) تفاصيل تبدو بسيطة في النموذج، مثل القدرة على حساب دالتيّ الجزء الصحيح والجزء الصحيح من العدد ، يمكن أن تُحدث فروقًا كبيرة في ما يمكن حسابه وكفاءة حسابه. مع ذلك، يكتب فافاسيس: "ربما تكون هذه الصعوبة متأصلة في الموضوع نفسه". ^{[ 3 ]} وفي سياق متصل، يشكو إريك باخ من أن تخصيص تكلفة وحدة لجميع العمليات الحسابية قد يُعطي فكرة مُضللة عن تعقيد المسألة في الحساب العملي، ^{[ 4 ]} ويشير فافاسيس أيضًا إلى أنه، حتى تاريخ نشر مراجعته، لم يكن لهذا العمل تأثير يُذكر على البحث العملي في الحوسبة العلمية . على الرغم من هذه المشكلات، يُوصي فافاسيس بالكتاب باعتباره مُلخصًا مُفيدًا وواضحًا لنظرية الحوسبة العددية. ^{[ 3 ]}

• التعقيد والحوسبة الحقيقية في أرشيف الإنترنت