BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2020 >
Volume 14, Number 1-2 >

Please use this identifier to cite or link to this item:

Title: Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables
Authors: Khoa, Phan Dang
Demetrovics, Janos
Thi, Vu Duc
Anh, Pham Viet
Keywords: Attribute Reduction
Consistent Decision Table
Rough 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.
ISSN: 1312-6555
Appears in Collections:Volume 14, Number 1-2

Files in This Item:

File Description SizeFormat
sjc-vol14-num1-2-2020-p27-p41.pdf303.05 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License