On the nonkeys

Vũ Đức Thi


In this paper we give some results about nonkeys. We show that for relation scheme the problem decide whether there is a nonkey having cardinality greater than or equal to a give integer m is NP-complete. However, for relation this problem can be solved by a polynomial time algorithm.

DOI: https://doi.org/10.15625/1813-9663/13/1/7979 Display counter: Abstract : 106 views. PDF (Tiếng Việt) : 54 views.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology