Extension complexity
উত্তল জ্যামিতি এবং পলিহেড্রাল কম্বিনেটরিক্সে, একটি উত্তল পলিটোপের সম্প্রসারণ জটিলতা হল উত্তল পলিটোপগুলির মধ্যে ক্ষুদ্রতম সংখ্যক দিক যা একটি অভিক্ষেপ হিসাবে থাকে। এই প্রসঙ্গে, এর একটি বর্ধিত গঠন বলা হয়; এর তুলনায় অনেক বেশি মাত্রা থাকতে পারে। সম্প্রসারণ জটিলতা কেবল তার সমন্বিত কাঠামোর উপর নয়, এর সুনির্দিষ্ট আকৃতির উপর নির্ভর করে। উদাহরণস্বরূপ, পার্শ্বযুক্ত নিয়মিত বহুভুজগুলির সম্প্রসারণ জটিলতা থাকে (বড় ও স্বরলিপি ব্যবহার করে প্রকাশ করা হয়), তবে কিছু অন্যান্য উত্তল-গনের সম্প্রসারণ জটিলতা কমপক্ষে এর সমানুপাতিক। যদি একটি পলিটোপ একটি সমন্বিত অপ্টিমাইজেশান সমস্যার সম্ভাব্য সমাধানগুলি বর্ণনা করে যার সম্প্রসারণ জটিলতা কম থাকে, তবে এটি সম্ভাব্যভাবে তার বর্ধিত গঠনে রৈখিক প্রোগ্রামিং ব্যবহার করে সমস্যার জন্য দক্ষ অ্যালগরিদম তৈরি করতে ব্যবহার করা যেতে পারে। এই কারণে, গবেষকরা এইভাবে উদ্ভূত পলিটোপগুলির সম্প্রসারণ জটিলতা অধ্যয়ন করেছেন। উদাহরণস্বরূপ, এটি জানা যায় যে মিলযুক্ত পলিটোপটির সূচকীয় সম্প্রসারণ জটিলতা রয়েছে। অন্যদিকে, নিয়মিত ম্যাট্রয়েডের স্বাধীন পলিটোপে বহুপদী সম্প্রসারণ জটিলতা রয়েছে। পলিটোপ প্রজেকশনের পরিবর্তে বর্ণালীর প্রজেকশন বিবেচনা করে এক্সটেনশন জটিলতার ধারণাকে রৈখিক প্রোগ্রামিং থেকে সেমিডিফাইনাইট প্রোগ্রামিং পর্যন্ত সাধারণীকরণ করা হয়েছে। তথ্যসূত্র পলিহেড্রাল কম্বিনেটরিক্স