Extension complexity
બહિર્મુખ ભૂમિતિ અને પોલીહેડ્રલ સંયોજનશાસ્ત્રમાં, બહિર્મુખ પોલીટોપની વિસ્તરણ જટિલતા એ બહિર્મુખ પોલીટોપમાંના પાસાઓ પૈકીની સૌથી નાની સંખ્યા છે જે પ્રક્ષેપણ તરીકે હોય છે. આ સંદર્ભમાં, તેને વિસ્તૃત રચના કહેવામાં આવે છે; તે તેના કરતા ઘણું વધારે પરિમાણ ધરાવી શકે છે. વિસ્તરણની જટિલતા તેના ચોક્કસ આકાર પર આધાર રાખે છે, માત્ર તેના સંયુક્ત માળખા પર નહીં. દાખલા તરીકે, બાજુઓ સાથેના નિયમિત બહુકોણમાં વિસ્તરણ જટિલતા હોય છે (મોટા ઓ નોટેશનનો ઉપયોગ કરીને વ્યક્ત કરવામાં આવે છે), પરંતુ કેટલાક અન્ય બહિર્મુખ-ગોનમાં વિસ્તરણ જટિલતા ઓછામાં ઓછી તેના પ્રમાણમાં હોય છે. જો સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાના શક્ય ઉકેલોનું વર્ણન કરતી પોલીટોપમાં વિસ્તરણની જટિલતા ઓછી હોય, તો તેનો ઉપયોગ સંભવિત રીતે તેની વિસ્તૃત રચના પર રેખીય પ્રોગ્રામિંગનો ઉપયોગ કરીને સમસ્યા માટે કાર્યક્ષમ અલ્ગોરિધમ્સ તૈયાર કરવા માટે થઈ શકે છે. આ કારણોસર, સંશોધકોએ આ રીતે ઉદ્ભવતા પોલીટોપ્સની વિસ્તરણ જટિલતાનો અભ્યાસ કર્યો છે. દાખલા તરીકે, તે જાણીતું છે કે મેળ ખાતી પોલીટોપમાં ઘાતાંકીય વિસ્તરણ જટિલતા છે. બીજી બાજુ, નિયમિત મેટ્રોઇડ્સના સ્વતંત્ર પોલીટોપ બહુપદી વિસ્તરણ જટિલતા ધરાવે છે. પોલીટોપ્સના અંદાજોને બદલે સ્પેક્ટ્રાહેડ્રાના અંદાજોને ધ્યાનમાં લઈને વિસ્તરણ જટિલતાની કલ્પનાને રેખીય પ્રોગ્રામિંગથી અર્ધ-અનંત પ્રોગ્રામિંગ સુધી સામાન્ય બનાવવામાં આવી છે. સંદર્ભો પોલિહેડ્રલ સંયોજનશાસ્ત્ર