Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định

Bài viết Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó.

Từ khóa: Độ phức tạp tính toán, Tập rút gọn trên bảng quyết định, Bài toán co NP, Bảng quyết định DS, Hệ thông tin, Tập rút gọn