Biredukty decyzyjne to rozszerzenie pojęcia reduktów decyzyjnych z teorii zbiorów przybliżonych, uwzględniające zarówno podzbiory atrybutów opisujących decyzję, jak i podzbiory obiektów, dla których te opisy są poprawne. Możemy powiedzieć bardziej formalnie, że biredukt decyzyjny jest reprezentowany jako para złożona z podzbioru obiektów oraz podzbioru atrybutów, dla których podzbiór atrybutów zapewnia poprawną klasyfikację dla wybranych obiektów.

W wystąpieniu zaprezentuję wyniki opracowane wspólnie z prof. dr. hab. Dominikiem Ślęzakiem, dotyczące złożoności obliczeniowej problemu znajdowania najprostszych poprawnych zespołów bireduktów decyzyjnych. Podczas prezentacji przypomnę podstawowe pojęcia z teorii złożoności obliczeniowej, a także pojęcie poprawnych zespołów bireduktów, które zilustruję przykładami. Następnie przedstawię dowód NP-zupełności (wersja decyzyjna) oraz NP-trudności (wersja optymalizacyjna) tego problemu.