Khóa tối tiểu và phản khóa là những khái niệm có vai trò quan trọng trong toán tử bao đóng. Bài viết giới thiệu về một bài toán tập không khóa của toán tử bao đóng. Bài toán này được bài viết chứng minh có độ phức tạp là NP-đầy đủ. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ Trường Đại học Khoa học ĐH Huế Tập 18 Số 1 2021 BÀI TOÁN NP-ĐẦY ĐỦ CỦA TOÁN TỬ BAO ĐÓNG Nguyễn Hoàng Sơn1 Trần Việt Khoa2 1 Khoa Toán Trường Đại học Khoa học Đại học Huế 2 Khoa CNTT Trường Đại học Khoa học Đại học Huế Email Ngày nhận bài 18 02 2021 ngày hoàn thành phản biện 21 5 2021 ngày duyệt đăng 02 6 2021 TÓM TẮT Khóa tối tiểu và phản khóa là những khái niệm có vai trò quan trọng trong toán tử bao đóng. Bài báo giới thiệu về một bài toán tập không khóa của toán tử bao đóng. Bài toán này được bài báo chứng minh có độ phức tạp là NP-đầy đủ. Từ khóa Toán tử bao đóng khóa tối tiểu phản khóa. 1. MỞ ĐẦU Toán tử bao đóng đã xuất hiện từ rất lâu trong toán cũng như toán ứng dụng. Tuy nhiên gần 30 năm trở lại đây toán tử bao đóng có nhiều ứng dụng quan trọng trong các lĩnh vực liên quan về dữ liệu như cơ sở dữ liệu các hệ suy diễn khai phá dữ liệu 1 4 6 9 . Ngoài ra các toán tử bao đóng này cũng có thể tìm thấy trong nhiều lý thuyết thời sự như siêu đồ thị matroid tập thô tập mờ trí tuệ nhân tạo lý thuyết quyết định 3 5 8 10 . Trong các vấn đề nghiên cứu về toán tử bao đóng thì khóa và phản khóa là được nhiều nhà nghiên cứu quan tâm nhất. Bài báo này cũng không ngoài mục đích đó. Trong bài báo này chúng tôi nghiên cứu độ phức tạp của bài toán xác định một tập cho trước có phải không khóa của toán tử bao đóng hay không. Cấu trúc bài báo chia làm 4 phần Sau phần mở đầu phần thứ 2 giới thiệu khái niệm toán tử bao đóng và một số khái niệm kết quả cơ sở liên quan. Phần thứ 3 chúng tôi giới thiệu và chứng minh một bài toán NP-đầy đủ về tập không khóa của toán tử bao đóng. Phần cuối cùng của bài báo là kết luận. 2. MỘT SỐ KHÁI NIỆM CƠ SỞ Mục này nhắc lại một số khái niệm và kết quả cơ sở. Các định nghĩa và kết quả này có thể tìm thấy trong 1 2 10 . 1 Bài toán NP-đầy đủ của toán tử bao đóng Cho U là một tập hữu hạn khác rỗng. Ký hiệu P U là tập lũy thừa của U . Ánh xạ L P U P U thỏa các điều kiện .
