الحوسبة والاستعصاء

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
الموسوعة الحرة

كتاب "الحوسبة والاستعصاء: دليل لنظرية اكتمال NP" هو كتاب دراسي من تأليف مايكل غاري وديفيد إس. جونسون . [ 1 ] كان أول كتاب يتناول حصريًا نظرية اكتمال NP والاستعصاء الحسابي . [ 2 ] يحتوي الكتاب على ملحق يقدم مجموعة شاملة من مسائل NP-كاملة (تم تحديثه في الطبعات اللاحقة). يُعتبر الكتاب الآن قديمًا في بعض جوانبه، إذ لا يغطي التطورات الحديثة مثل نظرية PCP . ومع ذلك، لا يزال يُطبع ويُعتبر مرجعًا كلاسيكيًا: ففي دراسة أجريت عام 2006، صنّف محرك البحث CiteSeer الكتاب كأكثر المراجع استشهادًا في أدبيات علوم الحاسوب. [ 3 ]

المشكلات المفتوحة

تضمن ملحق آخر من الكتاب مسائل لم يُعرف ما إذا كانت من فئة NP-كاملة أو من فئة P (أو لا هذه ولا تلك). وهذه المسائل (بأسمائها الأصلية) هي:

  1. تماثل الرسوم البيانية
    من المعروف أن هذه المشكلة تقع في فئة NP، ولكن من غير المعروف ما إذا كانت كاملة من فئة NP.
  2. التماثل الجزئي للرسم البياني (لرسم بياني ثابت H )
  3. جنس الرسم البياني
  4. إكمال الرسم البياني للوتر
  5. المؤشر اللوني [ 4 ]
  6. مشكلة التكافؤ في الشجرة الممتدة [ 5 ]
  7. بُعد الترتيب الجزئي
  8. جدولة المعالجات الثلاثة المقيدة بالأسبقية
    كانت هذه المشكلة لا تزال قائمة حتى عام 2016. [ 6 ]
  9. البرمجة الخطية
  10. التوحيد الكامل [ 7 ]
  11. رقم مركب
    من المعروف أن اختبار التركيب يقع في P، لكن تعقيد مشكلة تحليل الأعداد الصحيحة المرتبطة ارتباطًا وثيقًا لا يزال مفتوحًا.
  12. التثليث ذو الطول الأدنى [ 8 ]
    من المعروف أن المسألة رقم 12 هي مسألة صعبة من نوع NP، ولكن من غير المعروف ما إذا كانت تنتمي إلى فئة NP.

استقبال

بعد وقت قصير من ظهوره، تلقى الكتاب مراجعات إيجابية من قبل باحثين مرموقين في مجال علوم الحاسوب النظرية.

في مراجعته، يوصي رونالد ف. بوك بهذا الكتاب لكل من يرغب في التعرّف على موضوع اكتمال مسائل NP، ويشير تحديدًا إلى الملحق "المفيد للغاية" الذي يحتوي على أكثر من 300 مسألة حسابية صعبة من فئة NP. ويختتم قائلاً: "يحتاج علم الحاسوب إلى المزيد من الكتب كهذا الكتاب". [ 9 ]

يشيد هاري ر. لويس بالأسلوب الرياضي للمؤلفين قائلاً: "يُعدّ كتاب غاري وجونسون عرضًا وافيًا وواضحًا وعمليًا لمفهوم اكتمال NP. ومن الصعب، من نواحٍ عديدة، تخيّل معالجة أفضل لهذا الموضوع." كما يعتبر الملحق "فريدًا" و"نقطة انطلاق في محاولات إثبات أن مسائل جديدة كاملة NP". [ 10 ]

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

انظر أيضاً

مراجع

  1. ↑ غاري، م. ر.؛ جونسون ، د. س. (1979). فيكتور كلي (محرر). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية. سان فرانسيسكو، كاليفورنيا: دبليو . إتش . فريمان وشركاه. ISBN     0-7167-1045-5MR 0519066 .​ 338 صفحة. نسخة متوفرة على موقع archive.org
  2. ↑ جوريس هارتمانيس (1982). "الحواسيب والاستعصاء: دليل لنظرية اكتمال NP، مراجعة كتاب". مجلة SIAM Review . 24 (1): 90-91 . doi : 10.1137/1024022 . JSTOR 2029450 . 
  3. ↑ "المقالات الأكثر استشهاداً في علوم الحاسوب - سبتمبر 2006 (CiteSeer.Continuity)" . تم الاطلاع عليه بتاريخ 3 نوفمبر 2007 .
  4. ↑ NP-complete: هولير، إيان (نوفمبر 1981). "اكتمال NP لتلوين الحواف". مجلة SIAM للحوسبة . 10 (4): 718-720 . doi : 10.1137/0210055 .
  5. ^ في ص: Lovász، L. Lovász، L.؛ سوس، VT (محرران). الطرق الجبرية في نظرية الرسم البياني، المجلد الثاني (ندوة سيجد، 1978) . Colloquia Mathematica Societatis János Bolyai، 25. شمال هولندا. ص 495 – 517. 
  6. ↑ فان بيفرن، رينيه؛ بريديريك، روبرت؛ بولتو، لوران؛ كوموسيفيتش، كريستيان؛ تالمون، نمرود؛ ووجينجر، جيرهارد ج. (2016). "مسائل الجدولة المقيدة بالأسبقية والمُعَلمة بعرض الترتيب الجزئي". DOOR 2016: التحسين المتقطع وبحوث العمليات . سلسلة محاضرات في علوم الحاسوب . المجلد 9869. سبرينغر-فيرلاغ . الصفحات 105-120 . arXiv : 1605.00901 . doi : 10.1007/978-3-319-44914-2_9 .  
  7. ↑ في: سيمور، ب.د. (يونيو 1980). "تحليل المصفوفات المنتظمة" (ملف PDF) . مجلة نظرية التوافيق، السلسلة ب . 28 (3): 305-359 . doi : 10.1016/0095-8956(80)90075-1 .
  8. ↑ هل هي مسألة صعبة من نوع NP؟: مولزر، وولفغانغ؛ روت، غونتر (2008)، "التثليث ذو الوزن الأدنى هو مسألة صعبة من نوع NP"، مجلة ACM ، 55 (2)، المادة 11، arXiv : cs.CG/0601002 ، doi : 10.1145/1346330.1346336 ، MR 2417038 
  9. ↑ رونالد ف. بوك. مراجعة: الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . نشرة الجمعية الأمريكية للرياضيات (NS)، 3 (2)، ص 898 – 904، 1980
  10. ↑ هاري ر. لويس، مراجعة: الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، مجلة المنطق الرمزي ، المجلد 48 (2)، الصفحات 498-500 ، 1983
  11. ↑ لانس فورتناو ، كتب عظيمة: الحواسيب والاستعصاء: دليل لنظرية اكتمال NP بقلم مايكل ر. غاري وديفيد س. جونسون. مدونة التعقيد الحسابي، 30 أغسطس 2002.