อัลกอริทึมกาแล็กติกคืออัลกอริทึม ที่มีประสิทธิภาพทางทฤษฎี ( เชิงอะซิมโทติก ) ที่ทำลายสถิติแต่ไม่ได้ถูกนำมาใช้เนื่องจากข้อจำกัดในทางปฏิบัติ เหตุผลทั่วไปคือประสิทธิภาพที่เพิ่มขึ้นจะปรากฏเฉพาะกับปัญหาที่มีขนาดใหญ่มากจนไม่เคยเกิดขึ้น หรือความซับซ้อนของอัลกอริทึมมีมากกว่าประสิทธิภาพที่เพิ่มขึ้นเล็กน้อยในโลกแห่งความเป็นจริง อัลกอริทึมกาแล็กติกได้รับการตั้งชื่อโดยRichard Liptonและ Ken Regan ^{[ 1 ]}เนื่องจากจะไม่ถูกนำไปใช้กับชุดข้อมูลใด ๆ บนโลก

ถึงแม้ว่าอัลกอริทึมระดับกาแล็กซีจะไม่เคยถูกนำไปใช้ในทางปฏิบัติ แต่ก็อาจมีส่วนช่วยในด้านวิทยาศาสตร์คอมพิวเตอร์ ได้ :

• แม้ว่าอัลกอริทึมบางอย่างอาจใช้งานไม่ได้จริง แต่ก็อาจแสดงให้เห็นถึงเทคนิคใหม่ๆ ที่อาจนำไปใช้สร้างอัลกอริทึมที่ใช้งานได้จริงในอนาคตได้ ตัวอย่างเช่นความจุของช่องทางการสื่อสารดังที่แสดงด้านล่าง
• กำลังการประมวลผลที่มีอยู่อาจตามทันจุดเปลี่ยนผ่าน ทำให้ขั้นตอนวิธีที่เคยใช้ไม่ได้จริงกลายเป็นสิ่งที่ใช้ได้จริง ดูตัวอย่างเช่นรหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำด้านล่าง
• อัลกอริทึมที่ไม่เหมาะสมยังคงสามารถแสดงให้เห็นว่า ขอบเขต ที่คาดการณ์ไว้สามารถบรรลุได้ หรือว่าขอบเขตที่เสนอมานั้นผิดพลาด และด้วยเหตุนี้จึงพัฒนาทฤษฎีของอัลกอริทึม (ดูตัวอย่างเช่นอัลกอริทึมของ Reingold สำหรับการเชื่อมต่อในกราฟที่ไม่มีทิศทาง ) ดังที่ Lipton กล่าวไว้ว่า: ^{[ 1 ]}

  เพียงแค่นี้ก็อาจมีความสำคัญและมักเป็นเหตุผลที่ดีเยี่ยมในการค้นหาอัลกอริธึมดังกล่าวแล้ว ตัวอย่างเช่น หากพรุ่งนี้มีการค้นพบที่แสดงให้เห็นว่ามีอัลกอริธึมการแยกตัวประกอบที่มีขอบเขตเวลาขนาดใหญ่แต่พิสูจน์ได้ว่าเป็นเวลาแบบพหุนาม นั่นจะเปลี่ยนความเชื่อของเราเกี่ยวกับการแยกตัวประกอบ อัลกอริธึมนั้นอาจไม่เคยถูกนำมาใช้ แต่จะกำหนดทิศทางการวิจัยในอนาคตเกี่ยวกับการแยกตัวประกอบอย่างแน่นอน

  ในทำนองเดียวกัน อัลกอริทึมสมมุติสำหรับปัญหาความพึงพอใจของบูลีนที่มีขอบเขตเวลาขนาดใหญ่แต่เป็นพหุนาม เช่นแม้ว่าจะไม่สามารถใช้งานได้จริง แต่จะช่วยแก้ปัญหา P เทียบกับ NPซึ่งถือเป็นปัญหาเปิดที่สำคัญที่สุดในวิทยาศาสตร์คอมพิวเตอร์และเป็นหนึ่งในปัญหารางวัลแห่งสหัสวรรษ^{[ 2 ] [ 3 ]}${\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}$

ตัวอย่างของอัลกอริทึมกาแล็กติกคือวิธีที่เร็วที่สุดในการคูณตัวเลขสองตัว [ ^{4 ] ซึ่ง}ใช้การแปลงฟูริเยร์ 1729 มิติ ^{[ 5 ]}ต้องใช้การดำเนินการบิต แต่เนื่องจากค่าคงที่ที่ซ่อนอยู่ภายใต้สัญกรณ์บิ๊กโอมีขนาดใหญ่ จึงไม่เคยถูกนำมาใช้ในทางปฏิบัติ อย่างไรก็ตาม มันยังแสดงให้เห็นว่าทำไมอัลกอริทึมกาแล็กติกจึงอาจยังมีประโยชน์ ผู้เขียนกล่าวว่า "เราหวังว่าด้วยการปรับปรุงเพิ่มเติม อัลกอริทึมอาจใช้งานได้จริงสำหรับตัวเลขที่มีเพียงพันล้านหรือล้านล้านหลัก" ^{[ 5 ]}${\displaystyle O(n\log n)}$

การ ทดสอบความเป็นจำนวนเฉพาะ ของAKSนั้นยอดเยี่ยมมาก มันเป็นอัลกอริทึมที่มีพื้นฐานทางทฤษฎีดีที่สุดในบรรดาอัลกอริทึมที่รู้จักทั้งหมดที่สามารถรับจำนวนใดๆ มาตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ โดยเฉพาะอย่างยิ่ง มัน ทำงาน ได้ในเวลาพหุนามเป็นแบบกำหนดได้และถูกต้องอย่างไม่มีเงื่อนไขอัลกอริทึมอื่นๆ ที่รู้จักทั้งหมดนั้นด้อยกว่าอย่างน้อยหนึ่งเกณฑ์เหล่านี้ แต่ข้อบกพร่องนั้นเล็กน้อยและการคำนวณเร็วกว่ามาก ดังนั้นจึงถูกนำมาใช้แทน ในทางปฏิบัติ ECPPทำงานได้เร็วกว่า AKS มาก แต่ยังไม่เคยได้รับการพิสูจน์ว่าใช้เวลาพหุนาม การทดสอบ Miller–Rabinก็เร็วกว่า AKS มากเช่นกัน แต่ให้ผลลัพธ์เชิงความน่าจะเป็นเท่านั้น อย่างไรก็ตาม ความน่าจะเป็นของข้อผิดพลาดสามารถลดลงได้ถึงค่าที่น้อยมาก (เช่น) ซึ่งดีพอสำหรับการใช้งานจริง นอกจากนี้ยังมีเวอร์ชันแบบกำหนดได้ของการทดสอบ Miller-Rabin ซึ่งทำงานในเวลาพหุนามสำหรับอินพุตทั้งหมด แต่ความถูกต้องของมันขึ้นอยู่กับสมมติฐาน Riemann ทั่วไป (ซึ่งเป็นที่เชื่อกันอย่างกว้างขวาง แต่ยังไม่ได้รับการพิสูจน์) เนื่องจากมีทางเลือกอื่นที่เร็วกว่ามาก ทำให้ AKS ไม่ได้ถูกนำมาใช้ในทางปฏิบัติ ${\displaystyle <10^{-100}}$

การปรับปรุงครั้งแรกเหนือ การคูณเมทริกซ์แบบใช้กำลังทั้งหมด(ซึ่งใช้การดำเนินการ) คืออัลกอริทึม Strassen : อัลกอริทึมแบบเรียกซ้ำที่ใช้การดำเนินการ อัลกอริทึมนี้ไม่ซับซ้อนและถูกนำไปใช้ในทางปฏิบัติ การขยายเพิ่มเติมของสิ่งนี้โดยใช้ทฤษฎีกลุ่ม ที่ซับซ้อน ได้แก่อัลกอริทึม Coppersmith–Winogradและอัลกอริทึมที่พัฒนาต่อยอดจากนี้ซึ่งดีกว่าเล็กน้อย โดยใช้การดำเนินการ อัลกอริทึมเหล่านี้ซับซ้อน – “อย่างไรก็ตาม เราเน้นย้ำว่าการปรับปรุงดังกล่าวเป็นเพียงความสนใจทางทฤษฎีเท่านั้น เนื่องจากค่าคงที่ขนาดใหญ่ที่เกี่ยวข้องกับความซับซ้อนของการคูณเมทริกซ์อย่างรวดเร็วมักทำให้อัลกอริทึมเหล่านี้ไม่สามารถนำไปใช้ได้จริง” ^{[ 6 ]}${\displaystyle O(n^{3})}$${\displaystyle O(n^{2.807})}$${\displaystyle O(n^{2.373})}$

Claude Shannon ได้แสดง รหัสที่เรียบง่ายแต่เหมาะสมที่สุดในเชิงอะซิมโทติกซึ่งสามารถเข้าถึงความจุทางทฤษฎีของช่องทางการสื่อสารได้ โดยต้องกำหนดคำรหัสแบบสุ่มให้กับข้อความ -บิตที่เป็นไปได้ทุกข้อความ จากนั้นถอดรหัสโดยการหาคำรหัสที่ใกล้เคียงที่สุด หากเลือกค่าให้มีขนาดใหญ่พอ รหัสนี้จะเอาชนะรหัสที่มีอยู่ทั้งหมดและสามารถเข้าใกล้ความจุของช่องสัญญาณได้มากเท่าที่จะกำหนดได้ น่าเสียดายที่ค่าที่ใหญ่พอที่จะเอาชนะรหัสที่มีอยู่ทั้งหมดนั้นก็ไม่สามารถนำไปใช้ได้จริงเช่นกัน^{[ 7 ]}แม้ว่ารหัสเหล่านี้จะไม่เคยถูกนำมาใช้ แต่ก็เป็นแรงบันดาลใจให้เกิดการวิจัยเป็นเวลาหลายทศวรรษเกี่ยวกับอัลกอริทึมที่ใช้งานได้จริงมากขึ้น ซึ่งในปัจจุบันสามารถบรรลุอัตราที่ใกล้เคียงกับความจุของช่องสัญญาณได้มากเท่าที่จะกำหนดได้^{[ 8 ]}${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

ปัญหาของการตัดสินใจว่ากราฟมีไมเนอร์หรือ ไม่นั้นโดยทั่วไปแล้ว เป็นปัญหา NP-completeแต่ถ้าค่าคงที่ ปัญหานี้สามารถแก้ไขได้ในเวลาพหุนาม เวลาที่ใช้ในการทดสอบว่าเป็นไมเนอร์ของในกรณีนี้คือ[ ^{9 ] โดย}ที่คือจำนวนจุดยอดในและสัญกรณ์บิ๊กโอซ่อนค่าคงที่ที่ขึ้นอยู่กับแบบซูเปอร์เอ็กซ์โพ เนน เชียลของ ค่าคงที่นี้มากกว่าในสัญกรณ์ลูกศรขึ้นของ Knuthโดยที่คือจำนวนจุดยอดใน[ ^{10 ] แม้แต่}กรณีของก็ไม่สามารถคำนวณได้อย่างสมเหตุสมผล เนื่องจากค่าคงที่นี้มากกว่า 2 หารด้วย 4 หรือ 2 หาร ด้วย 65536 นั่น คือ${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle O(n^{2})}$${\displaystyle n}$${\displaystyle G}$${\displaystyle H}$${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$${\displaystyle h}$${\displaystyle H}$${\displaystyle h=4}$${\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}$

ใน ศัพท์เฉพาะทางด้าน การเข้ารหัสลับ "การเจาะระบบ" หมายถึงการโจมตีใดๆ ที่เร็วกว่าการโจมตีแบบเดาสุ่ม (brute force ) กล่าวคือ ทำการถอดรหัสทดลองหนึ่งครั้งสำหรับแต่ละคีย์ที่เป็นไปได้ สำหรับระบบการเข้ารหัสลับหลายระบบ การเจาะระบบเป็นที่รู้จัก แต่ในทางปฏิบัติยังไม่สามารถทำได้ด้วยเทคโนโลยีปัจจุบัน ตัวอย่างหนึ่งคือการโจมตีที่ดีที่สุดที่ทราบกันดีสำหรับAES 128 บิต ซึ่งใช้เพียงการดำเนินการ^{[ 11 ]}แม้ว่าจะไม่สามารถทำได้ในทางปฏิบัติ แต่การเจาะระบบในเชิงทฤษฎีสามารถให้ข้อมูลเชิงลึกเกี่ยวกับรูปแบบช่องโหว่ และบางครั้งนำไปสู่การค้นพบช่องโหว่ที่สามารถใช้ประโยชน์ได้ ${\displaystyle 2^{126}}$

เป็นเวลาหลายทศวรรษที่การประมาณค่าที่รู้จักกันดีที่สุดสำหรับปัญหาพนักงานขายเดินทางในปริภูมิเมตริกคืออัลกอริทึม Christofides ที่เรียบง่ายมาก ซึ่งสร้างเส้นทางที่ยาวกว่าค่าที่เหมาะสมที่สุดไม่เกิน 50% (อัลกอริทึมอื่นๆ จำนวนมากมัก จะ ทำได้ดีกว่ามาก แต่ไม่สามารถพิสูจน์ได้) ในปี 2020 ได้มีการค้นพบอัลกอริทึมใหม่ที่ซับซ้อนกว่ามากซึ่งสามารถเอาชนะอัลกอริทึมนี้ได้เป็นเปอร์เซ็นต์^{[ 12 ]}แม้ว่าจะไม่มีใครเปลี่ยนไปใช้อัลกอริทึมนี้เพื่อการปรับปรุงกรณีที่เลวร้ายที่สุดเพียงเล็กน้อย แต่ก็ยังถือว่ามีความสำคัญเพราะ "การปรับปรุงเล็กน้อยนี้สามารถทะลุผ่านทั้งอุปสรรคทางทฤษฎีและทางจิตวิทยาได้" ^{[ 13 ]}${\displaystyle 10^{-34}}$

อัลกอริทึมเดียว "การค้นหา Hutter" สามารถแก้ปัญหาที่กำหนดไว้อย่างดีได้ในเวลาที่เหมาะสมที่สุดแบบเชิงเส้นกำกับ ยกเว้นข้อจำกัดบางประการ อัลกอริทึมนี้ทำงานโดยการค้นหาผ่านอัลกอริทึมที่เป็นไปได้ทั้งหมด (ตามเวลาการทำงาน) ในขณะเดียวกันก็ค้นหาผ่านการพิสูจน์ ที่เป็นไปได้ทั้งหมด (ตามความยาวของการพิสูจน์) เพื่อหาการพิสูจน์ความถูกต้องสำหรับแต่ละอัลกอริทึม เนื่องจากการพิสูจน์ความถูกต้องมีขนาดจำกัด จึง "เพิ่ม" ค่าคงที่เท่านั้นและไม่ส่งผลกระทบต่อเวลาการทำงานแบบเชิงเส้นกำกับ อย่างไรก็ตาม ค่าคงที่นี้มีขนาดใหญ่มากจนอัลกอริทึมนี้ไม่สามารถนำไปใช้ได้จริง^{[ 14 ] [ 15 ]} ตัวอย่างเช่น หากการพิสูจน์ความถูกต้องที่สั้นที่สุดของอัลกอริทึมที่กำหนดมีความยาว 1,000 บิต การค้นหาจะตรวจสอบการพิสูจน์ที่เป็นไปได้อื่นๆ อย่างน้อย^2,999รายการก่อน

การค้นหาแบบฮัตเตอร์มีความเกี่ยวข้องกับการเหนี่ยวนำแบบโซโลมอนอฟซึ่งเป็นการวางรูปแบบอย่างเป็นทางการของการอนุมานแบบเบย์เซียน ทฤษฎี ที่คำนวณได้ทั้งหมด(ตามที่โปรแกรมได้นำไปใช้) ซึ่งอธิบายการสังเกตการณ์ก่อนหน้านี้ได้อย่างสมบูรณ์แบบ จะถูกนำมาใช้ในการคำนวณความน่าจะเป็นของการสังเกตการณ์ครั้งต่อไป โดยจะให้น้ำหนักกับทฤษฎีที่คำนวณได้สั้นกว่ามากกว่า อีกครั้ง การค้นหาคำอธิบายที่เป็นไปได้ทั้งหมดทำให้กระบวนการนี้ครอบคลุมกว้างขวางมาก

การอบชุบแบบจำลองเมื่อใช้ร่วมกับตารางการระบายความร้อนแบบลอการิทึม ได้รับการพิสูจน์แล้วว่าสามารถค้นหาจุดเหมาะสมที่สุดทั่วโลกของปัญหาการเพิ่มประสิทธิภาพใดๆ ได้^{[ 16 ]} อย่างไรก็ตาม ตารางการระบายความร้อนดังกล่าวส่งผลให้เวลาการทำงานไม่สามารถนำไปใช้ได้จริง และไม่เคยถูกนำมาใช้^{[ 17 ]} อย่างไรก็ตาม การที่ทราบว่าอัลกอริทึมในอุดมคตินี้มีอยู่จริง ทำให้เกิดรูปแบบที่ใช้งานได้จริงซึ่งสามารถค้นหาวิธีแก้ปัญหาที่ดีมาก (แม้ว่าจะไม่สามารถพิสูจน์ได้ว่าเหมาะสมที่สุด) สำหรับปัญหาการเพิ่มประสิทธิภาพที่ซับซ้อน^{[ 18 ] [ 19 ]}

อัลกอริทึม MST ที่ใช้เวลาเชิงเส้นที่คาดหวังสามารถค้นหาต้นไม้ครอบคลุมขั้นต่ำของกราฟในโดยที่คือจำนวนขอบ และคือจำนวนโหนดของกราฟ^{[ 20 ]}อย่างไรก็ตาม ค่าคงที่ที่ซ่อนอยู่ภายใต้สัญกรณ์ Big O นั้นมีขนาดใหญ่มากพอที่จะทำให้อัลกอริทึมใช้งานไม่ได้จริง การใช้งานนั้นมีให้ใช้งานได้ทั่วไป^{[ 21 ]}และเมื่อพิจารณาจากค่าคงที่การใช้งานที่ประเมินจากการทดลองแล้ว จะเร็วกว่าอัลกอริทึมของ Borůvka เฉพาะ สำหรับกราฟใน ซึ่งเท่านั้น^{[ 22 ]}${\displaystyle O(m+n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m+n>9\cdot 10^{151}}$

นักวิจัยได้ค้นพบอัลกอริทึมที่บรรลุประสิทธิภาพเชิงอะซิมโทติกที่ดีที่สุดที่พิสูจน์ได้^{[ 23 ]}ในแง่ของการแลกเปลี่ยนเวลาและพื้นที่ในตารางแฮช [ ^{24 ] แต่} ยังคงเป็นเพียงทฤษฎีเท่านั้น: "แม้ว่าตารางแฮชใหม่จะมีประสิทธิภาพที่ไม่เคยมีมาก่อน แต่ก็ไม่น่าจะมีใครพยายามสร้างมันในเร็วๆ นี้ มันซับซ้อนเกินไปที่จะสร้าง" ^{[ 25 ]}และ "ในทางปฏิบัติ ค่าคงที่มีความสำคัญจริงๆ ในโลกแห่งความเป็นจริง ตัวประกอบ 10 ถือเป็นตัวจบเกม" ^{[ 25 ]}

การเชื่อมต่อในกราฟแบบไม่มีทิศทาง (หรือที่รู้จักกันในชื่อ USTCON ซึ่งย่อมาจาก Undirected Source-Target CONnectivity) คือปัญหาในการตัดสินใจว่ามีเส้นทางระหว่างสองโหนดในกราฟแบบไม่มีทิศทางหรือไม่ หรือกล่าวอีกนัยหนึ่งคือ โหนดทั้งสองอยู่ในส่วนประกอบที่เชื่อมต่อกัน เดียวกันหรือไม่ เมื่ออนุญาตให้ใช้พื้นที่จัดเก็บข้อมูล วิธีแก้ปัญหาที่ใช้เวลาพหุนาม เช่นอัลกอริทึมของ Dijkstraเป็นที่รู้จักและใช้งานมานานหลายทศวรรษ แต่เป็นเวลาหลายปีที่ยังไม่ทราบว่าสามารถแก้ปัญหานี้ได้แบบกำหนดได้ในพื้นที่จัดเก็บข้อมูล (คลาสL ) หรือไม่ แม้ว่าจะทราบกันดีว่าสามารถทำได้ด้วยอัลกอริทึมแบบสุ่ม (คลาสRL ) ${\displaystyle O({\text{N}})}$${\displaystyle O({\text{log N}})}$

บทความที่ก้าวล้ำในปี 2008 โดยOmer Reingold แสดงให้เห็นว่า USTCON อยู่ใน Lจริงๆ[ ^{26 ]}ซึ่งเป็นอัลกอริทึมที่มีความต้องการพื้นที่ที่ดีกว่าในเชิงอะซิมโทติก อย่างไรก็ตาม^ค่าคงที่ขนาดใหญ่มากของอัลกอริทึมที่ถูกซ่อนไว้หมายความว่าในปัญหาที่สมจริงใดๆ มันใช้หน่วยความจำและเวลาในการคำนวณมากกว่าอัลกอริทึมที่เป็นที่รู้จักกันดีอย่างมาก แม้ว่าจะไม่ได้ถูกนำไปใช้ในทางปฏิบัติ แต่บทความนี้ก็ยังคงเป็นหลักสำคัญในทางทฤษฎี และได้รับการอ้างอิงมากกว่า 1,000 ครั้ง ณ ปี 2026 ${\displaystyle O({\text{log N}})}$${\displaystyle O({\text{N}})}$

รหัสตรวจสอบความเท่าเทียมกันความหนาแน่นต่ำหรือที่รู้จักกันในชื่อ LDPC หรือรหัส Gallager เป็นตัวอย่างของอัลกอริทึมที่ล้ำสมัยมากเมื่อพัฒนาขึ้นครั้งแรก แต่สามารถนำไปใช้ได้จริงเมื่อการคำนวณดีขึ้น เดิมทีคิดค้นโดยRobert G. Gallagerในวิทยานิพนธ์ปริญญาเอกของเขา^{[ 27 ]}ที่สถาบันเทคโนโลยีแมสซาชูเซตส์ในปี 1960 ^{[ 28 ] [ 29 ]}แม้ว่าประสิทธิภาพของมันจะดีกว่ารหัสอื่นๆ ในเวลานั้นมาก โดยสามารถเข้าถึงขอบเขต Gilbert–Varshamov สำหรับรหัสเชิงเส้นได้แต่รหัสเหล่านี้ก็ถูกละเลยเป็นส่วนใหญ่ เนื่องจากอัลกอริทึมการถอดรหัสแบบวนซ้ำมีค่าใช้จ่ายในการคำนวณสูงเกินไปสำหรับฮาร์ดแวร์ที่มีอยู่^{[ 30 ]}

ความสนใจในรหัส LDPC กลับมาอีกครั้งหลังจากมีการคิดค้นรหัสเทอร์โบ ที่เกี่ยวข้องอย่างใกล้ชิด (1993) ซึ่งอัลกอริทึมการถอดรหัสแบบวนซ้ำที่คล้ายกันนั้นมีประสิทธิภาพเหนือกว่ารหัสอื่นๆ ที่ใช้ในเวลานั้น ต่อมารหัส LDPC ก็ถูกค้นพบอีกครั้งในปี 1996 ^{[ 31 ]}และได้รับความนิยมในฐานะทางเลือกที่ไม่ต้องจดสิทธิบัตร^{[ 32 ]} แม้ว่าสิทธิบัตรของรหัสเทอร์โบจะหมดอายุไปแล้ว แต่รหัส LDPC ก็ยังมีข้อได้เปรียบทางเทคนิคบางประการ และถูกนำไปใช้ในแอปพลิเคชันต่างๆ มากมายในปัจจุบัน

การแบ่ง รูปหลายเหลี่ยมออกเป็นรูปสามเหลี่ยมที่ไม่ทับซ้อนกันเรียกว่าการแบ่งรูปหลายเหลี่ยมออกเป็นรูปสามเหลี่ยม Bernard Chazelleแสดงให้เห็นในปี 1991 ว่ารูปหลายเหลี่ยมแบบง่ายใดๆ ก็สามารถแบ่งออกเป็นรูปสามเหลี่ยมได้ในเวลาเชิงเส้น^{[ 33 ]} อย่างไรก็ตาม อัลกอริทึมที่เสนอมีความซับซ้อนอย่างมาก และมีอัลกอริทึมที่ง่ายกว่ามาก^{[ 34 ]}ที่มีประสิทธิภาพใกล้เคียงกับเชิงเส้นดังนั้นจึงใช้อัลกอริทึมเหล่านั้นแทน^{[ 35 ]} "งานของเขา [Chazelle] แสดงถึงความก้าวหน้าทางทฤษฎีที่สำคัญ อย่างไรก็ตาม อัลกอริทึม O(n) ของเขาปรากฏว่าเขียนโปรแกรมได้ยากมาก ดังนั้นเท่าที่ผู้เขียนทราบ ยังไม่มีการนำไปใช้งานจริง" ^{[ 36 ]}${\displaystyle O({\text{Nlog}}^{*}{\text{N}})}$