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|}$

ds.algorithms ds.data-structures partial-order order-theory search-problem a3nm
źródło

Zestawem mocy uporządkowanym przez włączenie jest DAG (z różnymi częściami jako wierzchołkami i jedną krawędzią między parami części, które są ze sobą połączone, zachowując tylko przechodnia redukcja tego wykresu w celu usunięcia zbędnych krawędzi wynikających z przechodniości). Naturalne wydaje się zadawanie tego samego pytania na temat arbitralnych DAG.

2^{| n |}

$2^{|n|}$

{1, . . ., n}

$\{1, ..., n\}$

a3nm

Odpowiedzi:

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. $t$ $n$ $t$

Yuval Filmus
źródło

Dzięki za tę niezwykle przydatną odpowiedź. Czy zdajesz sobie sprawę z uogólnień na arbitralne DAG (tj. Więcej niż przypadki szczególne w sekcji 5.2 Eiter i in.)?

a3nm

Nie, niestety nie.

Yuval Filmus

OK, i tak zaakceptuję tę odpowiedź. Dodatkowe uwagi: (1) ta odpowiedź dotyczy złożoności obliczeniowej, a nie złożoności liczby ocen (patrz ostatni przypadek: cstheory.stackexchange.com/a/14862/4795 ), oraz (2) dokładne otwarcie pytanie brzmi: „czy możesz nauczyć się monotonicznej funkcji boolowskiej w czasie wielomianowym w oraz jego liczbie minimów i maksimów”, nie ma nadziei, że zrobisz to w czasie wielomianowym w i liczbie maksimów, ponieważ może istnieć liniowa liczba maksimów ale wykładnicza liczba minimów (por. pkt 6.1 ust. 2 w wyżej wspomnianym badaniu).

P

$P$

n

$n$

n

$n$

a3nm

Zobacz moje inne pytanie cstheory.stackexchange.com/q/16258/4795, aby uzyskać informacje na temat złożoności globalnego zapytania w najgorszym przypadku dla dowolnych DAG.

a3nm

ponownie dualizacja monotoniczna (CNF ← → DNF) i DAG. brzmi bardzo podobnie do twierdzenia ze złożoności funkcji boolowskiej w książce Juknas, sekcja 9.4. „kryterium dolnych granic” thm 9.17