ความซับซ้อนที่สำคัญ (Essential complexity)เป็นการวัดเชิงตัวเลขที่กำหนดโดย Thomas J. McCabe, Sr. ในบทความปี 1976 ที่มีการอ้างอิงสูง ซึ่งเป็นที่รู้จักกันดีในฐานะผู้แนะนำ ความซับซ้อน แบบไซโคลมาติก (cyclomatic complexity ) McCabe นิยามความซับซ้อนที่สำคัญว่าเป็นความซับซ้อนแบบไซโคลมาติกของ CFG ( control-flow graph ) ที่ลดลงหลังจากแทนที่ (ลด) โครงสร้างควบคุมการเขียนโปรแกรมเชิงโครงสร้าง ทั้งหมด ซ้ำๆ กล่าวคือ โครงสร้างที่มีจุดเริ่มต้นเดียวและจุดสิ้นสุดเดียว (เช่น ลูป if-then-else และ while) ด้วยคำสั่งตัวแทนเดี่ยว^{[ 1 ] : 317 [ 2 ] : 80}

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

เพื่อหลีกเลี่ยงความสับสนระหว่างแนวคิดต่างๆ เกี่ยวกับการลดรูปเป็นโปรแกรมที่มีโครงสร้าง สิ่งสำคัญคือต้องสังเกตว่าบทความของ McCabe ได้กล่าวถึงและดำเนินการในบริบทของบทความปี 1973 โดยS. Rao Kosarajuซึ่งให้การปรับปรุง (หรือมุมมองทางเลือก) ของทฤษฎีบทโปรแกรมที่มีโครงสร้าง บทความสำคัญในปี 1966 ของ Böhm และ Jacopini แสดงให้เห็นว่าโปรแกรมทั้งหมดสามารถเขียนใหม่ได้โดยใช้โครงสร้างการเขียนโปรแกรมที่มีโครงสร้างเท่านั้น (หรือที่เรียกว่าโครงสร้าง D: ลำดับ, if-then-else และ while-loop) อย่างไรก็ตาม ในการแปลงโปรแกรมแบบสุ่มให้เป็นโปรแกรมที่มีโครงสร้าง อาจจำเป็นต้องแนะนำตัวแปรเพิ่มเติม (และใช้ในการทดสอบ) และโค้ดบางส่วนอาจซ้ำกัน^{[ 3 ]}

ในบทความของพวกเขา Böhm และ Jacopini ตั้งข้อสันนิษฐาน แต่ไม่ได้พิสูจน์ว่าจำเป็นต้องแนะนำตัวแปรเพิ่มเติมดังกล่าวสำหรับโปรแกรมที่ไม่มีโครงสร้างบางประเภทเพื่อแปลงให้เป็นโปรแกรมที่มีโครงสร้าง^{[ 4 ] : 236} ตัวอย่างของโปรแกรม (ที่เราทราบในปัจจุบัน) ที่ต้องใช้ตัวแปรเพิ่มเติมดังกล่าวคือลูปที่มีทางออกแบบมีเงื่อนไขสองทางอยู่ภายใน เพื่อแก้ไขข้อสันนิษฐานของ Böhm และ Jacopini นั้น Kosaraju ได้กำหนดแนวคิดการลดโปรแกรมที่เข้มงวดกว่าความเท่าเทียมกันของ Turing ที่ Böhm และ Jacopini ใช้ โดยพื้นฐานแล้ว แนวคิดการลดของ Kosaraju กำหนด นอกเหนือจากข้อกำหนดที่ชัดเจนว่าโปรแกรมทั้งสองต้องคำนวณค่าเดียวกัน (หรือไม่เสร็จสิ้น) เมื่อได้รับอินพุตเดียวกันแล้ว โปรแกรมทั้งสองต้องใช้การกระทำและภาคแสดงพื้นฐานเดียวกัน ซึ่งภาคแสดงพื้นฐานนั้นเข้าใจว่าเป็นนิพจน์ที่ใช้ในเงื่อนไข เนื่องจากข้อจำกัดเหล่านี้ การลดของ Kosaraju จึงไม่อนุญาตให้แนะนำตัวแปรเพิ่มเติม การกำหนดค่าให้กับตัวแปรเหล่านี้จะสร้างการกระทำพื้นฐานใหม่ และการทดสอบค่าของตัวแปรเหล่านี้จะเปลี่ยนเงื่อนไขที่ใช้ในเงื่อนไข การใช้แนวคิดการลดทอนที่เข้มงวดมากขึ้นนี้ Kosaraju ได้พิสูจน์สมมติฐานของ Böhm และ Jacopini กล่าวคือ ลูปที่มีทางออกสองทางไม่สามารถแปลงเป็นโปรแกรมที่มีโครงสร้างได้โดยไม่ต้องแนะนำตัวแปรเพิ่มเติมแต่เขายังไปไกลกว่านั้นและพิสูจน์ว่าโปรแกรมที่มีการหยุดหลายระดับ (จากลูป) ก่อให้เกิดลำดับชั้น ซึ่งทำให้สามารถหาโปรแกรมที่มีการหยุดหลายระดับที่มีความลึกn ได้เสมอ ซึ่งไม่สามารถลดทอนเป็นโปรแกรมที่มีการหยุดหลายระดับที่มีความลึกน้อยกว่าnได้โดยไม่ต้องแนะนำตัวแปรเพิ่มเติม^{[ 4 ] [ 5 ]}

McCabe ตั้งข้อสังเกตในบทความของเขาว่า เมื่อพิจารณาจากผลลัพธ์ของ Kosaraju เขาตั้งใจที่จะหาวิธีจับภาพคุณสมบัติที่สำคัญของโปรแกรมที่ไม่มีโครงสร้างในแง่ของกราฟการไหลของการควบคุม^{[ 1 ] : 315} เขาดำเนินการโดยการระบุถึงกราฟการไหลของการควบคุมที่สอดคล้องกับโปรแกรมที่ไม่มีโครงสร้างที่เล็กที่สุดก่อน (ซึ่งรวมถึงการแตกแขนงเข้าไปในลูป การแตกแขนงออกจากลูป และส่วนที่เทียบเท่ากับ if-then-else) ซึ่งเขาใช้ในการกำหนดทฤษฎีบทที่คล้ายคลึงกับทฤษฎีบทของ Kuratowskiและหลังจากนั้นเขาก็นำเสนอแนวคิดเรื่องความซับซ้อนที่สำคัญของเขาเพื่อให้ได้คำตอบเชิงมาตราส่วน ("การวัดโครงสร้างของโปรแกรม" ตามคำพูดของเขา) แทนที่จะเป็นคำตอบใช่/ไม่ใช่สำหรับคำถามที่ว่ากราฟการไหลของการควบคุมของโปรแกรมมีโครงสร้างหรือไม่^{[ 1 ] : 315} สุดท้าย แนวคิดของการลดขนาดที่ McCabe ใช้เพื่อลดขนาด CFG นั้นไม่เหมือนกับแนวคิดของ Kosaraju ในการลดผังงาน การลดรูปที่กำหนดไว้บน CFG ไม่รู้หรือไม่สนใจอินพุตของโปรแกรม มันเป็นเพียงการแปลงกราฟเท่านั้น^{[ 6 ]}

ตัวอย่างเช่น ส่วนของโปรแกรมภาษา C ต่อไปนี้ มีความซับซ้อนที่สำคัญเท่ากับ 1 เนื่องจาก คำสั่ง if ภายใน และคำสั่ง forสามารถลดทอนได้ กล่าวคือ เป็นโปรแกรมที่มีโครงสร้าง

สำหรับ( i = 0 ; i < 3 ; i ++ ) { ถ้า( a [ i ] == 0 ) b [ i ] += 2 ; }

ส่วนของโปรแกรมภาษาซีต่อไปนี้มีความซับซ้อนที่สำคัญเท่ากับสี่ และไวยากรณ์แบบ CFG ของมันไม่สามารถลดทอนได้ โปรแกรมจะค้นหาแถวแรกของ z ที่มีค่าเป็นศูนย์ทั้งหมดและใส่ดัชนีนั้นลงใน i หากไม่มีแถวใดที่มีค่าเป็นศูนย์ทั้งหมด โปรแกรมจะใส่ -1 ลงใน i

สำหรับ( i = 0 ; i < m ; i ++ ) { สำหรับ( j = 0 ; j < n ; j ++ ) { ถ้า( z [ i ][ j ] != 0 ) ไปที่non_zero ; } ไปที่found ; non_zero : } i = -1 ; found :

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

• ประวัติศาสตร์ของวิศวกรรมซอฟต์แวร์
• เส้นทางจากการตัดสินใจหนึ่งไปยังอีกการตัดสินใจหนึ่ง
• ความซับซ้อนแบบไซโคลมาติก