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

นั่นคือ co-NP คือเซตของปัญหาการตัดสินใจซึ่งมีพหุนาม⁠ ⁠${\displaystyle p(n)}$และเครื่องจักรทัวริงM ที่มีขอบเขตเวลาพหุนามอยู่ โดยที่สำหรับทุกอินสแตนซ์xนั้นxจะเป็นอินสแตนซ์ที่ไม่มีอยู่ก็ต่อเมื่อ: สำหรับใบรับรองc ที่เป็นไปได้บางใบ ที่มีความยาวจำกัดโดย⁠ ⁠${\displaystyle p(n)}$เครื่องจักรทัวริงM จะยอมรับคู่( x , c ) ^{[ 1 ]}

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

ตัวอย่างหนึ่งของ ปัญหา NP-completeคือปัญหาความสามารถในการทำให้เป็นจริงของบูลีน : กำหนดสูตรบูลีนมาให้ สูตรนั้นสามารถทำให้เป็นจริง ได้หรือไม่ (มีอินพุตที่เป็นไปได้ที่ทำให้สูตรให้ผลลัพธ์เป็นจริงหรือไม่)? ปัญหาที่ตรงกันข้ามถามว่า: "กำหนดสูตรบูลีนมาให้ สูตรนั้นไม่สามารถทำให้เป็นจริงได้หรือไม่ (อินพุตที่เป็นไปได้ทั้งหมดของสูตรให้ผลลัพธ์เป็นเท็จหรือไม่)?" เนื่องจากนี่คือส่วนเติมเต็มของปัญหาความสามารถในการทำให้เป็นจริง ใบรับรองสำหรับ กรณีที่ "ไม่"จึงเหมือนกับใบรับรองสำหรับกรณีที่"ใช่"จากปัญหา NP ดั้งเดิม: ชุดของการกำหนดค่าตัวแปรบูลีนที่ทำให้สูตรเป็นจริง ในทางกลับกัน ใบรับรองสำหรับ กรณีที่ "ใช่"สำหรับปัญหาที่ตรงกันข้าม (ไม่ว่าจะอยู่ในรูปแบบใด) จะมีความซับซ้อนเท่ากับใบรับรองสำหรับ กรณี ที่ "ไม่"ของปัญหาความสามารถในการทำให้เป็นจริง NP ดั้งเดิม

ปัญหาLเป็น ปัญหา co-NP-completeก็ต่อเมื่อLอยู่ใน co-NP และสำหรับปัญหาใดๆ ใน co-NP จะมีการลดรูปจากปัญหานั้นไปยังL ในเวลาพหุ นาม

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

ปัญหาที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์

⁠ ⁠${\displaystyle {\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}}$

ยังมีปัญหาที่ยังแก้ไม่ตกอีกมากมายในสาขาวิทยาการคอมพิวเตอร์

Pซึ่งเป็นคลาสของปัญหาที่แก้ได้ในเวลาพหุนาม เป็นเซตย่อยของทั้ง NP และ co-NP P ถือว่าเป็นเซตย่อยที่เข้มงวดในทั้งสองกรณี เนื่องจาก P ปิดภายใต้การเติมเต็ม และ NP และ co-NP เป็นส่วนเติมเต็ม จึงไม่สามารถเข้มงวดในกรณีหนึ่งและไม่เข้มงวดในอีกกรณีหนึ่งได้: ถ้า P เท่ากับ NP ก็ต้องเท่ากับ co-NP ด้วย และในทางกลับกัน^{[ 2 ]}

NP และ co-NP ถือว่าไม่เท่ากันเช่นกัน^{[ 3 ]}และความเท่าเทียมกันของพวกมันจะหมายถึงการยุบตัวของลำดับชั้นพหุนาม PH ไปยัง NP หากพวกมันไม่เท่ากัน จะไม่มีปัญหา NP-complete ใด ๆ ที่อยู่ใน co-NP และไม่มี ปัญหา co-NP-complete ใด ๆที่อยู่ใน NP ^{[ 4 ]}สามารถแสดงได้ดังนี้ สมมติเพื่อความขัดแย้งว่ามีปัญหา NP-complete X ที่อยู่ใน co-NP เนื่องจากปัญหาทั้งหมดใน NP สามารถลดรูปเป็นXได้ ดังนั้นสำหรับทุกปัญหาใน NP เราสามารถสร้างเครื่องจักรทัวริงแบบไม่กำหนดที่ตัดสินส่วนเติมเต็มในเวลาพหุนามได้ กล่าวคือ⁠ ⁠ จาก${\displaystyle {\textsf {NP}}\subseteq {\textsf {co-NP}}}$นี้จึงสรุปได้ว่าเซตของส่วนเติมเต็มของปัญหาใน NP เป็นเซตย่อยของเซตของส่วนเติมเต็มของปัญหาใน co-NP กล่าวคือ⁠ ⁠${\displaystyle {\textsf {co-NP}}\subseteq {\textsf {NP}}}$ดังนั้น⁠ ⁠${\displaystyle {\textsf {co-NP}}={\textsf {NP}}}$การพิสูจน์ว่าไม่มีปัญหา co-NP-complete ใดๆ ที่อยู่ใน NP ได้ ถ้า⁠ ⁠${\displaystyle {\textsf {NP}}\neq {\textsf {co-NP}}}$เป็นแบบสมมาตร

co-NP เป็นเซตย่อยของPHซึ่งเป็นเซตย่อยของPSPACE อีกที หนึ่ง

ตัวอย่างของปัญหาที่ทราบกันว่าอยู่ในทั้ง NP และ co-NP (แต่ไม่ทราบว่าอยู่ใน P) คือการแยกตัวประกอบจำนวนเต็ม : กำหนดจำนวนเต็มบวกmและnให้ตรวจสอบว่าmมีตัวประกอบที่น้อยกว่าnและมากกว่าหนึ่งหรือไม่ การเป็นสมาชิกใน NP นั้นชัดเจน หากmมีตัวประกอบดังกล่าว ตัวประกอบนั้นเองก็เป็นหลักฐานยืนยัน การเป็นสมาชิกใน co-NP ก็ตรงไปตรงมาเช่นกัน: เราสามารถแสดงรายการตัวประกอบเฉพาะของmซึ่งทั้งหมดมากกว่าหรือเท่ากับnซึ่งผู้ตรวจสอบสามารถยืนยันความถูกต้องได้โดยการคูณและการทดสอบความเป็นจำนวนเฉพาะ AKSปัจจุบันยังไม่ทราบว่ามีอัลกอริทึมเวลาพหุนามสำหรับการแยกตัวประกอบหรือไม่ หรือกล่าวอีกนัยหนึ่งคือการแยกตัวประกอบจำนวนเต็มอยู่ใน P ดังนั้นตัวอย่างนี้จึงน่าสนใจในฐานะที่เป็นหนึ่งในปัญหาที่เป็นธรรมชาติที่สุดที่ทราบว่าอยู่ใน NP และ co-NP แต่ไม่ทราบว่าอยู่ใน P ^{[ 5 ]}

• Complexity Zoo : coNP