Vertex enumeration problem
ریاضی میں، ایک پولیٹوپ، ایک پولی ہیڈرل سیل کمپلیکس، ایک ہائپرپلین ترتیب، یا مجرد جیومیٹری کے کسی دوسرے شے کے لیے ورٹیکس گنتی کا مسئلہ، شے کی کچھ رسمی نمائندگی کو دیکھتے ہوئے شے کے عمودی حصوں کے تعین کا مسئلہ ہے۔ ایک کلاسیکی مثال لکیری عدم مساوات کے ایک سیٹ کے ذریعہ مخصوص کنویکس پولیٹوپ کے عمودی حصوں کی گنتی کا مسئلہ ہے: جہاں A ایک m × n میٹرکس ہے، x متغیرات کا n × 1 کالم ویکٹر ہے، اور b متغیرات کا m × 1 کالم ویکٹر ہے۔ چوٹیوں کو دی گئی باؤنڈنگ عدم مساوات کو تلاش کرنے کے الٹا (دوہری) مسئلہ کو فیسیٹ گنتی کہا جاتا ہے (کنویکس ہل الگورتھم دیکھیں)۔ کمپیوٹیشنل پیچیدگی مسئلہ کی کمپیوٹیشنل پیچیدگی کمپیوٹر سائنس میں تحقیق کا موضوع ہے۔ غیر محدود پولی ہیڈرا کے لیے، مسئلہ این پی-ہارڈ کے طور پر جانا جاتا ہے، زیادہ واضح طور پر، ایسا کوئی الگورتھم نہیں ہے جو مشترکہ ان پٹ-آؤٹ پٹ سائز میں کثیر الجہتی وقت میں چلتا ہو، جب تک کہ پی = این پی نہ ہو۔ ڈیوڈ ایوس اور کومی فوکوڈا کا 1992 کا ایک مضمون ایک ریورس سرچ الگورتھم پیش کرتا ہے جو ایک پولیٹوپ کے v عمودی حصوں کو تلاش کرتا ہے جس کی وضاحت d طول و عرض میں n عدم مساوات کے غیر پیدا شدہ نظام کے ذریعہ کی جاتی ہے (یا، دوہری طور پر، d طول و عرض میں n پوائنٹس کے کنویکس ہل کے v پہلو، جہاں ہر پہلو بالکل d دیئے گئے پوائنٹس پر مشتمل ہوتا ہے) وقت O (ndv) اور خلا O (nd) میں۔ d طول و عرض میں n ہائپرپلین کے سادہ ترتیب میں v عمودی O (n2dv) وقت اور O (nd) خلائی پیچیدگی میں پائے جا سکتے ہیں۔ ایوس-فوکوڈا الگورتھم نے مبنی میٹروئڈز کے لیے کرس-کراس الگورتھم کو ڈھال لیا۔ نوٹ حوالہ جات جیومیٹرک الگورتھم لکیری پروگرامنگ پولی ہیڈرل کمبینٹوریکس پولی ہیڈرا ڈسکریٹ جیومیٹری عددی کمبینٹوریکس ریاضیاتی مسائل کمپیوٹیشنل جیومیٹری