Minimale Elemente eines monotonen Prädikats über dem Powerset

Man betrachte ein monotones Prädikat über dem Potenzsatz 2 | n | (bestellt durch Aufnahme). Mit "monoton" meine ich: ∀ x , y ∈ 2 | n | so dass x ⊂ y , wenn P ( x ) dann P ( y ) . Ich suche einen Algorithmus, um alle minimalen Elemente von P zu finden , dh x ∈ 2 | n | so dass P ( x $P$$2^{|n|}$$\forall x, y \in 2^{|n|}$$x \subset y$$P(x)$$P(y)$$P$$x \in 2^{|n|}$$P(x)$aber , ¬ P ( y ) . Da die Breite von 2 | n | Wenn , könnte es exponentiell viele minimale Elemente geben, und daher könnte die Laufzeit eines solchen Algorithmus im Allgemeinen exponentiell sein. Könnte es jedoch einen Algorithmus für diese Aufgabe geben, der in der Größe der Ausgabe polynomisch ist?$\forall y \subset x$$\neg P(y)$$2^{|n|}$$n \choose n/2$

[Kontext: Es wurde eine allgemeinere Frage gestellt , aber in den Antworten wurde kein Versuch unternommen, die Komplexität des Algorithmus in Bezug auf die Größe der Ausgabe zu bewerten. Wenn ich zum Beispiel annehme, dass es nur ein minimales Element gibt, kann ich nach dieser Antwort eine binäre Suche durchführen und sie finden. Wenn ich jedoch weiterhin nach minimalen Elementen suchen möchte, muss ich die aktuellen Informationen zu pflegen , dass die Suche fortgesetzt werden kann, ohne Zeit auf das zu verschwenden, was bereits bekannt ist. Ist es möglich, dies zu tun und alle minimalen Elemente in der Polynomzeit in der Größe der Ausgabe zu finden?]$P$

Idealerweise würde ich gerne verstehen, ob dies mit allgemeinen DAGs möglich ist, aber ich weiß bereits nicht, wie ich die Frage für beantworten soll .$2^{|n|}$

Ihr Problem ist in der Lernliteratur als "Lernen von monotonen Funktionen mithilfe von Mitgliedschaftsabfragen" bekannt. Eine Klasse von monotonen Funktionen, für die man alle Zwischenzeiten identifizieren kann, wird als "polynomial lernbar unter Verwendung von Mitgliedschaftsabfragen" bezeichnet.

Es scheint, dass die Existenz eines polynomialen Zeitalgorithmus noch offen ist. Schmulevich et al. beweisen, dass "fast alle monotonen Booleschen Funktionen mithilfe von Mitgliedschaftsabfragen polynomisch lernbar sind". Wenn wir auch verlangen, dass der te Interm in n und t im Zeitpolynom erzeugt wird , dann ist das Problem äquivalent zur monotonen Dualisierung, wie von Bioch und Ibaraki gezeigt . Hier ist eine Umfrage zur monotonen Dualisierung.$t$$n$$t$