تعقيد الامتداد

في الهندسة المحدبة والتوافقية متعددة السطوح ، تعقيد امتداد متعدد السطوح المحدب${\displaystyle P}$هو أصغر عدد من الأوجه بين متعددات الوجوه المحدبة${\displaystyle Q}$التي لديها${\displaystyle P}$كإسقاط. في هذا السياق،${\displaystyle Q}$يُطلق عليه اسم الصيغة الموسعة لـ${\displaystyle P}$قد يكون له بُعد أعلى بكثير من${\displaystyle P}$[ ^{1 ] [ 2 ] [ 3 ]​}

يعتمد تعقيد الامتداد على الشكل الدقيق لـ${\displaystyle P}$ليس فقط على بنيتها التوافقية. على سبيل المثال، المضلعات المنتظمة ذات${\displaystyle n}$تتميز الجوانب بتعقيد الامتداد${\displaystyle O(\log n)}$(معبرًا عنها باستخدام ترميز Big O )، ^{[ 4 ] [ 5 ]} ولكن بعض الدوال المحدبة الأخرى${\displaystyle n}$تتمتع الأشكال ذات الأضلاع المتعددة بتعقيد امتداد يتناسب على الأقل مع${\displaystyle {\sqrt {n}}}$[ ^{5 ]​}

إذا كان متعدد السطوح الذي يصف الحلول الممكنة لمسألة تحسين توافقي يتميز بتعقيد امتداد منخفض، فمن الممكن استخدامه لتصميم خوارزميات فعالة لهذه المسألة، باستخدام البرمجة الخطية على صيغتها الموسعة. لهذا السبب، درس الباحثون تعقيد امتداد متعددات السطوح الناتجة بهذه الطريقة. ^{[ 6 ]} على سبيل المثال، من المعروف أن متعدد السطوح المطابق يتميز بتعقيد امتداد أسي. ^{[ 7 ]} من ناحية أخرى، يتميز متعدد السطوح المستقل للمصفوفات المنتظمة بتعقيد امتداد متعدد الحدود. ^{[ 8 ]}

كما تم تعميم مفهوم تعقيد الامتداد من البرمجة الخطية إلى البرمجة شبه المحددة ، وذلك من خلال النظر في إسقاطات الأطياف بدلاً من إسقاطات متعددات الوجوه. ^{[ 9 ] [ 10 ]}