Trong lý thuyết độ phức tạp tính toán, các bài toán co-NP-đầy đủ là những bài toán khó nhất trong co-NP. Nếu tồn tại thuật toán giải một bài toán co-NP-đầy đủ nhanh chóng thì có thể dùng thuật toán đó để giải mọi bài toán co-NP nhanh chóng.Một bài toán co-NP-đầy đủ là phần bù của một bài toán NP-đầy đủ. Có những bài toán trong cả NP và co-NP. Vẫn chưa biết hai tập hợp có bằng nhau hay không nhưng có nhiều khả năng là chúng khác nhau. Xem co-NP và NP-đầy đủ để biết thêm chi tiết.Fortune (1979)Lỗi harv: không có mục tiêu: CITEREFFortune1979 (trợ giúp) chứng minh rằng nếu một ngôn ngữ thưa là co-NP-đầy đủ (hoặc thậm chí chỉ co-NP-khó), thì P = NP,[1]. Đây là một yếu tố cơ bản dẫn đến định lý Mahaney.