Minimalne elementy monotonicznego predykatu nad zestawem mocy

Rozważ monotoniczny predykat $P$ nad zestawem mocy $2^{|n|}$(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: $\forall x, y \in 2^{|n|}$tak, że $x \subset y$ , jeśli $P(x)$ to $P(y)$ . Szukam algorytmu, aby znaleźć wszystkie minimalne elementy $P$ , tj. $x \in 2^{|n|}$takie, że $P(x)$ale $\forall y \subset x$ , $\neg P(y)$ . Ponieważ szerokość $2^{|n|}$jest $n \choose n/2$ , może istnieć wykładniczo wiele minimalnych elementów, a zatem czas działania takiego algorytmu może być generalnie wykładniczy. Czy jednak może istnieć algorytm dla tego zadania, który ma wielomian wielkości wyjściowej?

[Kontekst: Bardziej ogólne pytanie został poproszony , ale nie było żadnej próby w odpowiedzi do oceny złożoności algorytmu w wielkości produkcji. Jeśli założę na przykład, że istnieje tylko jeden minimalny element, mogę wykonać wyszukiwanie binarne po tej odpowiedzi i znaleźć ją. Jeśli jednak chcę kontynuować znajdowanie bardziej minimalnych elementów, muszę zachować aktualne informacje o $P$ w taki sposób, aby kontynuowanie wyszukiwania było praktycznie możliwe bez marnowania czasu na to, co już wiadomo. Czy można to zrobić i znaleźć wszystkie minimalne elementy w czasie wielomianowym o wielkości wyjściowej?]

Idealnie chciałbym zrozumieć, czy można to zrobić za pomocą ogólnych DAG, ale już nie wiem, jak odpowiedzieć na pytanie dla .$2^{|n|}$

Twój problem jest znany w literaturze przedmiotu jako „uczenie się funkcji monotonicznych za pomocą zapytań członkowskich”. Klasa funkcji monotonicznych, dla których można zidentyfikować wszystkie mintermy, znana jest jako „wielomianowo możliwy do nauczenia się za pomocą zapytań członkowskich”.

Wydaje się, że istnienie algorytmu wielomianowego czasu jest nadal otwarte. Schmulevich i in. udowodnić, że „Prawie wszystkie monotoniczne funkcje boolowskie można nauczyć wielomianowo za pomocą zapytań członkowskich”. Jeśli wymagane jest, by p minterm być generowane w czasie wielomian i , problem jest równoważne monotonicznej dualization, jak pokazano Bioch i Ibaraki . Oto ankieta dotycząca dualizacji monotonicznej.n $t$$n$$t$