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

${\displaystyle Ax\leq b}$

โดยที่Aคือ เมทริกซ์ขนาด m × n , xคือ เวกเตอร์คอลัมน์ขนาด n × 1 ของตัวแปร และbคือ เวกเตอร์คอลัมน์ขนาด m × 1 ของค่าคงที่ ปัญหาผกผัน ( คู่ขนาน ) ของการหาอสมการขอบเขตที่กำหนดโดยจุดยอดเรียกว่าการแจงนับเหลี่ยมมุม (ดูอัลกอริทึมของเปลือกนูน )

ความซับซ้อนในการคำนวณของปัญหานี้เป็นหัวข้อการวิจัยในวิทยาศาสตร์คอมพิวเตอร์สำหรับโพลีเฮดราที่ไม่จำกัด ปัญหานี้เป็นที่ทราบกันว่าเป็น NP-hard กล่าวคือ ไม่มีอัลกอริทึมใดที่ทำงานในเวลาพหุนามในขนาดอินพุต-เอาต์พุตรวม เว้นแต่ว่า P=NP ^{[ 2 ]}

บทความปี 1992 โดยDavid AvisและKomei Fukuda ^{[ 3 ]}นำเสนออัลกอริทึมการค้นหาแบบย้อนกลับซึ่งค้นหา จุดยอด vจุดของโพลีโทปที่กำหนดโดยระบบ อสมการ n ที่ไม่เสื่อม สภาพใน มิติ d (หรือในทางกลับกัน ด้าน v ด้านของส่วนนูนของ จุด nจุดใน มิติ dโดยที่แต่ละด้านมี จุดที่กำหนด d จุดพอดี ) ในเวลาO ( ndv ) และพื้นที่ O( nd ) จุดยอด vจุดในการจัดเรียง ระนาบไฮเปอร์ n ระนาบ อย่างง่าย ใน มิติ dสามารถพบได้ในเวลา O( n ² dv ) และความซับซ้อนของพื้นที่ O( nd ) อัลกอริทึม Avis–Fukuda ปรับอัลกอริทึมไขว้สำหรับเมทริกซ์แบบมีทิศทาง

บทความปี 2025 โดย Zelin Dong, Fenglei Fan, Huan Xiong และ Tieyong Zeng ^{[ 4 ]}ได้นำกฎ Zeroมาใช้ในอัลกอริทึมการค้นหาย้อนกลับที่ได้รับการปรับให้เหมาะสม กฎการหมุนนี้ได้รับการพิสูจน์แล้วว่าสามารถยุติได้ภายในdขั้นตอน ผ่านการวิเคราะห์คุณสมบัติอย่างเป็นทางการ กฎนี้ได้ถูกรวมเข้ากับอัลกอริทึมที่มีประสิทธิภาพ ทำให้ได้ความซับซ้อนของเวลา O( n ² d ² (vv _d ) + ndv _d ) โดยที่v _dหมายถึงจำนวนพจนานุกรมที่ไปถึงสถานะสุดท้ายใน การหมุน d ครั้งภาย ใต้กฎ Zeroซึ่งจะกลายเป็น O( nd ⁴ v ) สำหรับการจัดเรียงแบบง่าย ซึ่งปรับปรุงจากความซับซ้อน O( n ² dv ) ของรุ่นก่อนหน้า