Bài toán NP - Đầy đủ của toán tử bao đóng

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: nhson.math@gmail.com 
 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 PU() là tập lũy thừa của . Ánh 
xạ LPUPU:()() → thỏa các điều kiện sau: 
 (L1) X L X () 
 (L2) XYLXLY  ()() 
 (L3) L( L (X ) ) L( ) X = 
với mọi X Y, U  , được gọi là một toán tử bao đóng (TTBĐ) trên U . Ký hiệu C L() U là 
tập tất cả các TTBĐ trên U . 
 Xét TTBĐ L C L U () và KU . Tập K được gọi là khóa của L nếu L() K U = . 
Một khóa được gọi là tối tiểu nếu với mọi aK thì L() K a− 1 không phải là một 
khóa. Ký hiệu tập tất cả khóa tối tiểu của L là K e y L(). 
 Một tập con KU−1  được gọi là phản khóa của nếu L() K U−1 và với mọi 
a U − K −1 thìL() K a− U1 =. Ký hiệu A n t i k e y L() là tập tất cả các phản khóa của . 
 Mối quan hệ giữa khóa tối tiểu và phản khóa của TTBĐ như sau: 
Mệnh đề 2.1. [9] 
 KeyLUAntikeyL()()=− . 
Ví dụ 2.1. Các ánh xạ sau là các TTBĐ cơ sở: 
 1) Ánh xạ tối đại mPUPU:()() → xác định bởi mXU()= với mọi XU , và 
 Keym()=  , Antikey() m =. 
 2) Ánh xạ đồng nhất iPUPU:()() → cho bởi iXX()= với mọi , và 
 KeyiU()= , Antikey(): i= U − a a U  . 
 3) Ánh xạ tịnh tiến tM :()() P U→ P U xác định bởi tM () X= M X với M là tập 
 con cho trước của U , và KeytUM()M =−  , 
 Antikey(): tUaaUMM =− −  
3. KẾT QUẢ 
 Xét TTBĐ L CL() U . Đặt SX= XL: kh«ng ph¶i lµ mét khãa cña . Như 
vậy, rõ ràng S là họ các tập không phải khóa của TTBĐ L . Từ định nghĩa phản khóa, 
suy ra AntikeyL() cũng là họ các tập không phải khóa tối đại của . 
1 Ký hiệu X− a,, X  a X − Y tương ứng lần lượt thay cho X\,,\ a X a X Y với mọi 
XYU,  và aU 
 2 
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) 
 Như chúng ta đã biết các tập không phải khóa tối đại đóng vai trò quan trọng 
trong nhiều bài toán thú vị của TTBĐ cũng như nhiều vấn đề liên quan khác. Trong mục 
này, chúng ta sẽ giới thiệu một bài toán NP-đầy đủ liên quan đến tập không khóa của 
TTBĐ. Bài toán này được mô tả như sau 
Bài toán 3.1. (Bài toán không khóa của TTBĐ) 
Dữ kiện: TTBĐ L C L U () và một số nguyên dương k sao cho kU ||. 
Câu hỏi: Có tồn tại một tập XS sao cho kX ||? 
 Để chứng minh tính NP-đầy đủ của Bài toán 3.1, chúng ta sẽ sử dụng Bài toán 
NP-đầy đủ tập độc lập đã biết sau 
Bài toán 3.2. [7] (Bài toán tập độc lập) 
Dữ kiện: Một số nguyên dương và một đồ thị vô hướng G V= E( , ) với V là tập các 
đỉnh và E là tập các cạnh. 
Câu hỏi: Có tồn tại một tập độc lập I sao cho kI ||? 
Định lý 3.1. Bài toán 3.1 là NP-đầy đủ. 
Chứng minh. 
 Dễ thấy Bài toán 3.1 thuộc lớp NP, vì tồn tại thuật toán không đơn định giải Bài 
toán 3.1 như sau: 
 • Sinh một tập con XU sao cho ||Xk một cách không đơn định. 
 • Kiểm tra trong thời gian đa thức X có phải là tập không khóa của TTBĐ L 
 hay không. 
 Bây giờ chúng ta sẽ chứng minh Bài toán 3.2 quy dẫn đa thức về Bài toán 3.1. 
Thật vậy, xét đồ thị vô hướng với kV ||. Ta xây dựng ánh xạ 
fPUPU:()() → như sau: 
 VXu nÕu vE , = 
 fX()= 
 X ng•îc l¹i
ở đây UV= . Chú ý rằng với mỗi XE ta có fXiX()() = . Dễ thấy fCL U () và f 
được xây dựng trong thời gian đa thức theo kích thước của G . 
 Theo định nghĩa đồ thị, rõ ràng E là một siêu đồ thị đơn trên V . Từ định nghĩa 
khóa tối tiểu và TTBĐ được xây dựng như trên, ta có KeyfE()= . Do đó, có thể thấy 
X không phải một khóa của nếu và chỉ nếu u, vX  với mọi u, vE . Vậy, X 
không phải khóa của nếu và chỉ nếu là một tập độc lập của . 
 3 
Bài toán NP-đầy đủ của toán tử bao đóng 
4. KẾT LUẬN 
 Như vậy, bài báo đã giới thiệu bài toán không khóa của TTBĐ, và chứng minh 
được bài toán này có độ phức tạp là NP-đầy đủ. Điều này có nghĩa rằng bài toán không 
khóa của TTBĐ là bài toán rất khó, không có thuật toán đa thức giải bài toán này nếu 
NP P . 
 TÀI LIỆU THAM KHẢO 
[1]. W. W. Armstrong, Dependency structures of database relationships, Information processing 74 
 (1974), 580-583. 
[2]. F. E. Bennett, Li Sheng Wu, On minimum matrix representation of closure operations, Discrete 
 Applied Mathematics, 26 (1990) 25-40. 
[3]. C. Berge, Hypergraphs: combinatorics of finite sets, North-Holland, Amsterdam, 1989. 
[4]. G. Burosch, J. Demetrovics, G. O. H. Katona (1987), The poset of closures as a model of changing 
 databases, Order, 127-142. 
[5]. N. Caspard, B. Monjardet, The lattices of closure systems, closure operators, and implicational 
 systems on a finite set: a survey, Discrete Applied Mathematics, 127 (2003) 241-269. 
[6]. J. Demetrovics, G. Hencsey , L. Libkin , I. Muchnik, On the interaction between closure operations 
 and choice functions with applications to relational databases, Acta Cybernetica, 10 (1992) 129-139. 
[7]. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-
 Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Company, 
 San Francisco, 1979. 
[8]. H. Mao, S. Liu, Posets and closure operators relative to matroids, Matematika, (2012) 77-85. 
[9]. Nguyen Hoang Son, Vu Duc Thi, Some the combinatorial characteristics of closure operations, 
 Algebra and Discrete Mathematics, 28 (2019) 144-156. 
[10]. Z. Pawlak, Rough sets-Theoretical aspects of reasoning about data, Kluwer Academic Publishers, 
 The Netherlands, 1991. 
 4 
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) 
 NP-COMPLETE PROBLEM OF CLOSURE OPERATIONS 
 Nguyen Hoang Son1*, Tran Viet Khoa2 
 1 Faculty of Mathematics, University of Sciences, Hue University 
 2 Faculty of Information Technology, University of Sciences, Hue University 
 * Email: nhson.math@gmail.com 
 ABSTRACT 
 Minimal keys and antikeys that are concepts play an important role in the closure 
 operations. The paper presents a problem about the nonkey set of the closure 
 operations. The paper proves that this problem has NP-complete complexity. 
 Keywords: antikey, closure operations, minimal key. 
 Nguyễn Hoàng Sơn sinh ngày 28/06/1973 tại Thừa Thiên Huế. Năm 
 1995, ông tốt nghiệp đại học ngành Toán - Tin tại Trường Đại học Tổng 
 hợp Huế. Ông nhận bằng thạc sỹ Tin học tại Trường Đại học Bách khoa 
 Hà Nội năm 1998, và nhận học vị Tiến sĩ chuyên ngành Đảm bảo toán 
 học cho máy tính và hệ thống tính toán tại Viện Công nghệ Thông Tin, 
 Viện Hàn lâm Khoa học và Công nghệ Việt Nam năm 2006. Hiện ông 
 công tác tại Trường Đại học Khoa học, Đại học Huế. 
 Lĩnh vực nghiên cứu: Khoa học dữ liệu, toán rời rạc, lý thuyết độ phức tạp 
 tính toán. 
 Trần Việt Khoa sinh ngày 19/06/1972 tại Thanh Hóa. Tốt nghiệp đại học 
 Tổng hợp Huế năm 1995 chuyên ngành Toán-Tin. Ông nhận bằng thạc 
 sỹ Tin học năm 2005 tại Trường Đại học Khoa học, Đại học Huế. Hiện 
 nay công tác tại Khoa Công nghệ Thông tin, trường Đại học Khoa học, 
 Đại học Huế. 
 Lĩnh vực nghiên cứu: Toán học rời rạc, cấu trúc dữ liệu và giải thuật, các 
 hệ quản trị cơ sở dữ liệu. 
 5 
Bài toán NP-đầy đủ của toán tử bao đóng 
 6