ในทฤษฎีความซับซ้อนของการคำนวณส่วนเติมเต็มของปัญหาการตัดสินใจคือปัญหาการตัดสินใจที่เกิดจากการสลับคำตอบใช่และไม่ใช่^{[ 1 ]}หรือกล่าวอีกนัยหนึ่ง หากเรากำหนดปัญหาการตัดสินใจเป็นเซตของสตริง จำกัด ส่วนเติมเต็มของเซตนี้เหนือโดเมนคงที่บางอย่างก็คือปัญหาส่วนเติมเต็มของมัน^{[ 2 ]}

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

มีการลดทอนแบบทัวริงจากทุกปัญหาไปสู่ปัญหาส่วนเติมเต็ม^{[ 4 ]}การดำเนินการส่วนเติมเต็มเป็นการผกผันหมายความว่ามัน "ยกเลิกตัวเอง" หรือส่วนเติมเต็มของส่วนเติมเต็มคือปัญหาดั้งเดิม

เราสามารถสรุปสิ่งนี้ไปยังส่วนเติมเต็มของคลาสความซับซ้อนซึ่งเรียกว่าคลาสส่วนเติมเต็มซึ่งเป็นเซตของส่วนเติมเต็มของทุกปัญหาในคลาส^{[ 5 ]}หากคลาสเรียกว่าCส่วนเติมเต็มของคลาสนั้นโดยทั่วไปจะเรียกว่าco-Cโปรดสังเกตว่านี่ไม่ใช่ส่วนเติมเต็มของคลาสความซับซ้อนเองในฐานะเซตของปัญหา ซึ่งโดยทั่วไปจะมีปัญหามากกว่านี้มาก

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

การปิดของคลาสความซับซ้อนใดๆ ภายใต้การลดทอนของทัวริง คือ ซูเปอร์เซตของคลาสนั้นซึ่งปิดภายใต้คอมพลีเมนต์ การปิดภายใต้คอมพลีเมนต์คือคลาสที่เล็กที่สุดดังกล่าว หากคลาสถูกตัดกับคอมพลีเมนต์ของมัน เราจะได้ซับเซต (อาจว่างเปล่า) ที่ปิดภายใต้คอมพลีเมนต์

คลาสความซับซ้อนเชิงกำหนดทุกคลาส ( DTIME ( f ( n )), DSPACE ( f ( n )), สำหรับf ( n ใดๆ )) ปิดภายใต้ส่วนเติมเต็ม^{[ 8 ]}เพราะสามารถเพิ่มขั้นตอนสุดท้ายให้กับอัลกอริทึมที่กลับคำตอบได้ง่ายๆ วิธีนี้ใช้ไม่ได้กับคลาสความซับซ้อนเชิงไม่กำหนด เพราะหากมีเส้นทางการคำนวณทั้งที่ยอมรับและปฏิเสธอินสแตนซ์เฉพาะ และเส้นทางทั้งหมดกลับคำตอบ ก็ยังคงมีเส้นทางที่ยอมรับและปฏิเสธอยู่ดี ดังนั้นทั้งเครื่องจักรดั้งเดิมและเครื่องจักรที่แก้ไขแล้วจึงยอมรับอินสแตนซ์

ในทำนองเดียวกัน คลาสความน่าจะเป็น เช่นBPP , ZPP , BQPหรือPPที่นิยามอย่างสมมาตรโดยคำนึงถึงกรณีที่เป็นใช่และไม่ใช่จะปิดภายใต้คอมพลีเมนต์ ในขณะที่คลาสเช่นRPและco-RPที่กำหนดความน่าจะเป็นด้วยข้อผิดพลาดด้านเดียว จะไม่ปิดภายใต้คอมพลีเมนต์ (เท่าที่ทราบในปัจจุบัน)

ผลลัพธ์เชิงความซับซ้อนที่น่าประหลาดใจที่สุดบางส่วนที่แสดงให้เห็นจนถึงปัจจุบัน แสดงให้เห็นว่าชั้นความซับซ้อนNLและSL นั้นปิดภายใต้ส่วนเติมเต็ม (ดูทฤษฎีบท Immerman–Szelepcsényi ) ในขณะที่ก่อนหน้านี้เป็นที่เชื่อกันอย่างกว้างขวางว่าไม่เป็นเช่นนั้น แต่ปัจจุบันนี้ผลลัพธ์ดังกล่าวไม่น่าประหลาดใจอีกต่อไปแล้ว เนื่องจากเรารู้ว่าSLเท่ากับLซึ่งเป็นชั้นเชิงกำหนด

ทุกคลาสที่มีค่าต่ำในตัวเอง จะปิดภายใต้ส่วนเติมเต็ม