ในทฤษฎีความซับซ้อนปัญหาการคำนวณที่เป็นco-NP-completeคือปัญหาที่ยากที่สุดในco-NPในแง่ที่ว่าปัญหาใดๆ ใน co-NP สามารถแปลงรูปแบบใหม่ได้เป็นกรณีพิเศษของปัญหา co-NP-complete ใดๆ โดยมีค่าใช้จ่ายเพิ่มเติมเพียงระดับพหุนามเท่านั้น หากPแตกต่างจาก co-NP แล้ว ปัญหา co-NP-complete ทั้งหมดจะไม่สามารถแก้ไขได้ในเวลาพหุนาม หากมีวิธีแก้ปัญหา co-NP-complete ได้อย่างรวดเร็ว อัลกอริทึมนั้นก็สามารถนำมาใช้แก้ปัญหา co-NP ทั้งหมดได้อย่างรวดเร็วเช่นกัน

แนวคิดนี้มีความน่าสนใจเป็นพิเศษในการศึกษาปัญหา P=NP และในเรื่อง NP-completeness ดูรายละเอียดเพิ่มเติมได้ ที่ co-NPและNP-complete

ปัญหาการตัดสินใจCเรียกว่า co-NP-complete ถ้ามันอยู่ในco-NPและถ้าทุกปัญหาใน co-NP สามารถลดรูป many-one ในเวลาพหุนามไปยังมันได้^{[ 1 ]}ซึ่งหมายความว่าสำหรับทุกปัญหา co-NP Lจะมีอัลกอริทึมเวลาพหุนามที่สามารถแปลงอินสแตนซ์ใด ๆ ของLไปเป็นอินสแตนซ์ของC ที่มี ค่าความจริงเดียวกันได้ ผลที่ตามมาคือ ถ้าเรามีอัลกอริทึมเวลาพหุนามสำหรับCเราก็สามารถแก้ปัญหา co-NP ทั้งหมดได้ในเวลาพหุนาม

แนวคิดเรื่อง co-NP-completeness นั้นไม่ได้แตกต่างจากแนวคิดเรื่อง NP-completeness มากนัก เนื่องจากปัญหา NP ทุกปัญหาสามารถแปลงเป็นปัญหา co-NP ได้อย่างง่ายดาย และในทางกลับกัน โดยการสลับ "ยอมรับ" และ "ปฏิเสธ" ดังนั้น ปัญหา NP-complete ทุก ปัญหาจึงสามารถแปลงเป็นปัญหา co-NP-complete ได้เช่นกัน

อย่างไรก็ตาม นี่ไม่ได้หมายความว่าแนวคิดเรื่องความสมบูรณ์ของ co-NP นั้นไร้ประโยชน์ เพราะเป็นไปได้ที่จะมีปัญหาที่เป็น NP แต่ไม่ใช่ co-NP การสลับป้ายกำกับ "ยอมรับ" และ "ปฏิเสธ" ส่งผลให้เกิดปัญหาที่เป็น co-NP แต่ไม่ใช่ NP ปัญหาที่ว่า NP=co-NP นั้นยังคงเป็นปัญหาที่ยังไม่มีคำตอบ เนื่องจากปัญหาของ P=NP ก็เป็นปัญหาที่ยังไม่มีคำตอบเช่นกัน ดังนั้นตัวอย่างปัญหาทั้งหมดที่ทราบใน จึงติด อยู่ในP${\displaystyle {\mathsf {NP}}\cap {\mathsf {conNP}}}$

ตัวอย่างหนึ่งของปัญหา co-NP-complete คือการตรวจสอบสัจนิรันดร์ซึ่งเป็นปัญหาในการพิจารณาว่า สูตร บูลีน ที่กำหนดให้ เป็นสัจนิรันดร์หรือไม่ กล่าวคือ การกำหนดค่าจริง/เท็จที่เป็นไปได้ทั้งหมดให้กับตัวแปรจะให้ผลลัพธ์เป็นข้อความที่เป็นจริงหรือไม่ ปัญหานี้เป็นส่วนเสริมของปัญหาความพึงพอใจของบูลีนซึ่งถามว่ามี การกำหนดค่าดังกล่าว อย่างน้อยหนึ่งรายการหรือไม่ และเป็นปัญหา NP-complete ^{[ 1 ]}ในรายละเอียดเพิ่มเติม:

• หากสูตรใดสูตรหนึ่งไม่ใช่สัจนิรันดร์ ก็สามารถพิสูจน์ได้ว่าไม่จริงในเวลาพหุนามโดยการกำหนดค่าอย่างชัดเจน
• หากสูตรนั้นสามารถพิสูจน์ได้ ก็สามารถพิสูจน์ได้ในเวลาพหุนามโดยการกำหนดค่าอย่างชัดเจน

ถ้าภาษาสปาร์ส ใดๆ เป็นแบบ co-NP-complete (หรือแม้แต่ co-NP-hard) แล้วP = NP [ ^{2 ] ผลลัพธ์}นี้ใช้ในทฤษฎีบทของ Mahaney ^{[ 3 ]}

• Complexity Zoo : coNPC