Złożoność obliczeniowa problemu szukania najprostszych poprawnych zespołów bireduktów decyzyjnych

Speaker(s)

Dr Sebastian Stawicki

Affiliation

UW & QED Software

Language of the talk

Polish

Date

Nov. 29, 2024, 4 p.m.

Room

room 4060

Seminar

Seminar Intelligent Systems

---

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.

 

---