مشكلة تعداد الرؤوس

في الرياضيات، تُعرف مسألة تعداد رؤوس متعدد السطوح ، أو مُركب الخلايا متعدد السطوح ، أو ترتيب المستويات الفائقة ، أو أي شكل آخر من أشكال الهندسة المنفصلة ، ​​بأنها مسألة تحديد رؤوس هذا الشكل بمعلومية تمثيل رسمي له. ومن الأمثلة الكلاسيكية على ذلك مسألة تعداد رؤوس متعدد السطوح المحدب المحدد بمجموعة من المتباينات الخطية : ^{[ 1 ]}

${\displaystyle Ax\leq b}$

حيث A مصفوفة من الرتبة m × n ، و x متجه عمودي من الرتبة n × 1 للمتغيرات، و b متجه عمودي من الرتبة m × 1 للثوابت. تُسمى المسألة العكسية ( الثنائية ) لإيجاد المتباينات الحدية بمعلومية الرؤوس بتعداد الأوجه (انظر خوارزميات الغلاف المحدب ).

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

في مقال نُشر عام ١٩٩٢ بقلم ديفيد أفيس وكومي فوكودا ^{[ ٣ ]} ، عُرضت خوارزمية بحث عكسي لإيجاد رؤوس متعددة السطوح v المُعرَّفة بنظام غير مُنحط من n متباينات في d بُعد (أو، بصورة مُزدوجة، أوجه الغلاف المحدب لـ n نقطة في d بُعد، حيث يحتوي كل وجه على d نقطة مُعطاة بالضبط ) في زمن O ( ndv ) ومساحة O( nd ). ويمكن إيجاد رؤوس v في ترتيب بسيط لـ n مستويات فائقة في d بُعد في زمن O( n²dv ) ومساحة O( ^nd ) . وقد عدّلت خوارزمية أفيس-فوكودا خوارزمية التقاطع للمصفوفات الموجهة.

في مقال نُشر عام 2025 من قِبل زيلين دونغ، وفينغلي فان، وهوان شيونغ، وتييونغ زينغ ^{[ 4 ]،} تم إدخال قاعدة الصفر في خوارزمية بحث عكسي مُحسَّنة. وقد ثبت ^أن هذه القاعدة المحورية تُنهي العملية في غضون ^d خطوة . ومن خلال تحليل رسمي لخصائصها، تم دمج القاعدة في خوارزمية فعالة، محققةً تعقيدًا زمنيًا قدره O( n²d² (vv₀d ) ₊ ndv₀d _{) ، حيث يُمثل v₀d} ^عدد القواميس التي تصل إلى الحالة النهائية في d خطوة محورية بالضبط وفقًا لقاعدة الصفر . ويُصبح هذا التعقيد O( nd₀d₀ ) للترتيبات البسيطة، مُحسِّنًا بذلك التعقيد O( ^n²dv₀ ) للخوارزمية السابقة.

• أفيس، ديفيد ؛ فوكودا، كومي (ديسمبر 1992). "خوارزمية محورية للأغلفة المحدبة وحصر رؤوس الترتيبات والمجسمات متعددة السطوح" . الهندسة المنفصلة والحسابية . 8 (1): 295-313 . doi : 10.1007/BF02293050 . MR 1174359 . 

• زيلين دونغ؛ فنجلي فان؛ هوان شيونغ؛ تييونج زينج (نوفمبر 2025). “خوارزمية فعالة لتعداد قمة الترتيب”. الرياضيات التطبيقية المنفصلة . 380 : 649 – 671.