Co-NP-đầy đủ

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.

Định nghĩa

Một bài toán quyết định C là co-NP-đầy đủ nếu nó nằm trong co-NP và mọi bài toán trong co-NP đều quy về nó trong thời gian đa thức. Nghĩa là với mọi bài toán L trong co-NP, tồn tại một thuật toán chạy trong thời gian đa thức để biến đổi một trường hợp của L thành một trường hợp của C với cùng kết quả. Do đó nếu tồn tại thuật toán thời gian đa thức cho C, thì ta có thể giải mọi bài toán trong co-NP trong thời gian đa thức.

Ví dụ

Một ví dụ của bài toán co-NP-đầy đủ là hằng đúng: bài toán yêu cầu xác định xem một biểu thức Boole có là một hằng đúng hay không; nghĩa là có phải với mọi giá trị đúng/sai của các biến, biểu thức luôn nhận giá trị đúng. Bài toán này có liên hệ với bài toán thỏa mãn biểu thức lôgic, trong đó câu hỏi là có tồn tại bộ giá trị các biến sao cho biểu thức nhận giá trị đúng.

Tham khảo

1. “A note on sparse complete sets”, SIAM Journal on Computing, 8 (3): 431–433, 1979 Đã bỏ qua văn bản “S. Fortune” (trợ giúp)