Extension complexity
کنویکس جیومیٹری اور پولی ہیڈرل کمبینٹوریکس میں، کنویکس پولیٹوپ کی توسیعی پیچیدگی کنویکس پولیٹوپس کے پہلوؤں کی سب سے چھوٹی تعداد ہے جو ایک پروجیکشن کے طور پر ہوتی ہے۔ اس تناظر میں، ایک توسیعی تشکیل کہا جاتا ہے ؛ اس کی جہت اس سے کہیں زیادہ ہو سکتی ہے۔ توسیع کی پیچیدگی کا انحصار اس کی عین مطابق شکل پر ہوتا ہے، نہ کہ صرف اس کی مشترکہ ساخت پر۔ مثال کے طور پر، اطراف والے باقاعدہ کثیر الاضلاعات میں توسیعی پیچیدگی ہوتی ہے (جس کا اظہار بڑے O اشارے کا استعمال کرتے ہوئے کیا جاتا ہے)، لیکن کچھ دوسرے کنویکس-گونز میں توسیعی پیچیدگی کم از کم اس کے متناسب ہوتی ہے۔ اگر ایک پولیٹوپ جو کسی مشترکہ اصلاح کے مسئلے کے قابل عمل حل کو بیان کرتا ہے اس میں توسیع کی پیچیدگی کم ہے، تو اسے ممکنہ طور پر اس مسئلے کے لیے موثر الگورتھم وضع کرنے کے لیے استعمال کیا جا سکتا ہے، اس کی توسیعی تشکیل پر لکیری پروگرامنگ کا استعمال کرتے ہوئے۔ اس وجہ سے، محققین نے اس طرح سے پیدا ہونے والے پولی ٹاپس کی توسیع کی پیچیدگی کا مطالعہ کیا ہے۔ مثال کے طور پر، یہ معلوم ہے کہ مماثل پولیٹوپ میں ایکسپونینشل ایکسٹینشن پیچیدگی ہوتی ہے۔ دوسری طرف، باقاعدہ میٹروئڈز کے آزاد پولیٹوپ میں کثیر الجہتی توسیع کی پیچیدگی ہوتی ہے۔ توسیع کی پیچیدگی کے تصور کو لکیری پروگرامنگ سے لے کر سیمیڈفائنٹ پروگرامنگ تک عام کیا گیا ہے، پولی ٹاپس کے پروجیکشنز کی جگہ سپیکٹراہڈرا کے پروجیکشنز پر غور کرکے۔ حوالہ جات پولی ہیڈرل کمبینٹوریکس