On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables

Authors

  • János Demetrovics Institute for Computer and Control (SZTAKI) Hungarian Academy of Sciences
  • Vu Duc Thi Institute of Information Technology VNU, Vietnam
  • Nguyen Long Giang Institute of Information Technology VAST, Vietnam
  • Tran Huy Duong Institute of Information Technology VAST, Vietnam

Keywords:

Decision Table, Reduct, Relation, Relation Schema, Minimal Set, Time Complexity

Abstract

In recent years, rough set approach computing issues concerning
reducts of decision tables have attracted the attention of many researchers.

In this paper, we present the time complexity of an algorithm
computing reducts of decision tables by relational database approach. Let
DS = (U, C ∪ {d}) be a consistent decision table, we say that A ⊆ C is a
relative reduct of DS if A contains a reduct of DS. Let s = <C ∪ {d} , F>
be a relation schema on the attribute set C ∪ {d}, we say that A ⊆ C is
a relative minimal set of the attribute d if A contains a minimal set of d.
Let Qd be the family of all relative reducts of DS, and Pd be the family of
all relative minimal sets of the attribute d on s.

We prove that the problem whether Qd ⊆ Pd is co-NP-complete.
However, the problem whether Pd ⊆ Qd is in P .

Downloads

Published

2022-04-13

Issue

Section

Articles