Trzy przykłady problemów zapewne NP-trudnych z dziedzin przetwarzania i eksploracji danych

Przedstawię przykłady trzech obszarów problemów optymalizacyjnych, które najprawdopodobniej są NP-trudne, lecz których NP-trudność nie jest jeszcze udowodniona.

Pierwszy przykład dotyczy wyznaczania z danych przybliżonych sieci Bayesowskich o minimalnej liczbie krawędzi, czyli minimalnych grafów acyklicznych, które kodują za pomocą d-separacji przybliżone niezależności warunkowe pomiędzy atrybutami, o zadanym stopniu przybliżenia wyznaczanym z danych.

Drugi przykład dotyczy ładowania danych do granularnej bazy danych typu Infobright, gdzie dane są przechowywane w paczkach powstałych w wyniku dekompozycji ze względu na atrybuty i podzbiory wierszy, a gdzie zależy nam na minimalizacji liczby paczek danych o zbyt heterogenicznej zawartości.

Trzeci przykład dotyczy wyznaczania z danych stabilnych podzbiorów atrybutów w formie przybliżonych reduktów decyzyjnych, które to podzbiory mają szansę pozostać reduktami na zadowalającym poziomie przybliżenia dla zmieniających się danych.