Vertex enumeration problem
गणित में, एक पॉलीटोप, एक पॉलीहेड्रल कोशिका परिसर, एक हाइपरप्लेन व्यवस्था, या असतत ज्यामिति की किसी अन्य वस्तु के लिए शीर्ष गणना समस्या, वस्तु के कुछ औपचारिक प्रतिनिधित्व को देखते हुए वस्तु के शीर्षों के निर्धारण की समस्या है। एक शास्त्रीय उदाहरण रैखिक असमानताओं के एक समूह द्वारा निर्दिष्ट एक उत्तल पॉलीटोप के शीर्षों की गणना की समस्या हैः जहाँ A एक m × n मैट्रिक्स है, x चर का एक n × 1 कॉलम वेक्टर है, और b स्थिरांक का एक m × 1 कॉलम वेक्टर है। शीर्षों को देखते हुए सीमा असमानताओं को खोजने की व्युत्क्रम (दोहरी) समस्या को पहलू गणना कहा जाता है (उत्तल पतवार एल्गोरिदम देखें)। कम्प्यूटेशनल जटिलता समस्या की कम्प्यूटेशनल जटिलता कंप्यूटर विज्ञान में अनुसंधान का विषय है। अनबाउंडेड पॉलीहेड्रा के लिए, समस्या को एनपी-हार्ड के रूप में जाना जाता है, अधिक सटीक रूप से, कोई एल्गोरिथ्म नहीं है जो संयुक्त इनपुट-आउटपुट आकार में बहुपद समय में चलता है, जब तक कि पी = एनपी न हो। डेविड एविस और कोमेई फुकुदा का 1992 का एक लेख एक रिवर्स-सर्च एल्गोरिथ्म प्रस्तुत करता है जो डी आयामों में एन असमानताओं की एक गैर-अपक्षयी प्रणाली द्वारा परिभाषित एक पॉलीटोप के वी शीर्षों को पाता है (या, दोहरी रूप से, डी आयामों में एन बिंदुओं के उत्तल पतवार के वी पहलू, जहां प्रत्येक पहलू में बिल्कुल डी दिए गए बिंदु होते हैं) समय ओ (एन. डी. वी) और स्पेस ओ (एन. डी) में। d आयामों में n हाइपरप्लेन की एक सरल व्यवस्था में v शीर्ष O (n2dv) समय और O (nd) अंतरिक्ष जटिलता में पाए जा सकते हैं। एविस-फुकुदा एल्गोरिथ्म ने उन्मुख मेट्रॉइड के लिए क्रिस-क्रॉस एल्गोरिथ्म को अनुकूलित किया। टिप्पणियाँ संदर्भ ज्यामितीय एल्गोरिदम रैखिक प्रोग्रामिंग पॉलीहेड्रल संयोजन पॉलीहेड्रा असतत ज्यामिति संख्यात्मक संयोजन गणितीय समस्याएं कम्प्यूटेशनल ज्यामिति