Some NP-Complete Problems for Attribute Reduction in Consistent Decision Tables

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.