ในเรขาคณิตนูนและการรวมรูปทรงหลายเหลี่ยมความซับซ้อนของการขยายของรูปทรงหลายเหลี่ยมนูน คือจำนวนหน้าตัด ที่น้อยที่สุด ในบรรดารูปทรงหลายเหลี่ยมนูนที่มีเป็นภาพฉาย ในบริบทนี้เรียกว่าสูตรขยายของ; มันอาจมีมิติที่สูงกว่ามาก^{[ 1 ] [ 2 ] [ 3 ]}${\displaystyle P}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle P}$

ความซับซ้อนของการขยายขึ้นอยู่กับรูปร่างที่แน่นอนของไม่ใช่แค่โครงสร้างเชิงการจัดเรียงเท่านั้น ตัวอย่างเช่นรูปหลายเหลี่ยมปกติที่มีด้าน มีความซับซ้อนของการขยาย(แสดงโดยใช้สัญกรณ์บิ๊กโอ ) ^{[ 4 ] [ 5 ]}แต่รูปหลายเหลี่ยมนูนอื่นๆ บางรูป^มีความซับซ้อนของการขยายอย่างน้อยก็เป็นสัดส่วนกับ[ ^{5 ]}${\displaystyle P}$${\displaystyle n}$${\displaystyle O(\log n)}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$

หากโพลีโทปที่อธิบายโซลูชันที่เป็นไปได้สำหรับ ปัญหา การเพิ่มประสิทธิภาพเชิงคอมบินาทอริกมีความซับซ้อนในการขยายต่ำ อาจใช้โพลีโทปนี้เพื่อคิดค้นอัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาดังกล่าว โดยใช้การเขียนโปรแกรมเชิงเส้นบนสูตรที่ขยายออกไป ด้วยเหตุนี้ นักวิจัยจึงได้ศึกษาความซับซ้อนในการขยายของโพลีโทปที่เกิดขึ้นในลักษณะนี้^{[ 6 ]}ตัวอย่างเช่น เป็นที่ทราบกันว่าโพลีโทปการจับคู่มีความซับซ้อนในการขยายแบบเลขชี้กำลัง^{[ 7 ]}ในทางกลับกันโพลีโทปความเป็นอิสระของเมทริกซ์ปกติมีความซับซ้อนในการขยายแบบพหุนาม^{[ 8 ]}

แนวคิดเรื่องความซับซ้อนของการขยายยังได้รับการขยายจากการเขียนโปรแกรมเชิงเส้นไปสู่การเขียนโปรแกรมแบบกึ่งกำหนดโดยพิจารณาการฉายภาพของสเปกตรัมเฮดราแทนการฉายภาพของโพลีโทป^{[ 9 ] [ 10 ]}