Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/4034

 Title: Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables Authors: Khoa, Phan DangDemetrovics, JanosThi, Vu DucAnh, Pham Viet Keywords: Attribute ReductionNP-CompleteComplexityConsistent Decision TableRough Set Theory Issue Date: 2020 Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences Citation: Serdica Journal of Computing, Vol. 14, No 1-2, (2020), 27p-41p Abstract: Over recent years, the research of attribute reduction for general decision systems and, in particular, for consistent decision tables has attracted great attention from the computer science community due to the emerge of big data. It has been known that, for a consistent decision table, we can derive a polynomial time complexity algorithm for finding a reduct. In addition, finding redundant properties can also be done in polynomial time. However, finding all reduct sets in a consistent decision table is a problem with exponential time complexity. In this paper, we study complexity of the problem for finding a certain class of reduct sets. In particular, we make use of a new concept of relative reduct in the consistent decision table. We present two NP-complete problems related to the proposed concept. These problems are related to the cardinality constraint and the relative reduct set. On the basis of this result, we show that finding a reduct with the smallest cardinality cannot be done by an algorithm with polynomial time complexity. URI: http://hdl.handle.net/10525/4034 ISSN: 1312-6555 Appears in Collections: Volume 14, Number 1-2

Files in This Item:

File Description SizeFormat