A logic approach for reducing the computational complexity of the attribute reduction problem

Since the generation all of minimal subsets of attributes (MSAs) of a dataset is NP-hard, usually attribute reduction algorithms (ARAs) use some heuristics to find a small part of MSAs with the risk to overlook the best solutions. There is a discernibility function (DF)-based ARA for generating all MSAs, but often failing to find them even for medium sized datasets due to memory overflows. In this study, it is proposed such a partition of a DF on which the computational complexity of each part cannot be exceeded the square root of the computational complexity of the DF in whole.