Elementos mínimos de un predicado monotónico sobre el conjunto

Considere un predicado monótono sobre el conjunto de potencia 2 | n | (ordenado por inclusión). Por "monotónico" quiero decir: ∀ x , y ∈ 2 | n | tal que x ⊂ y , si P ( x ) entonces P ( y ) . Estoy buscando un algoritmo para encontrar todos los elementos mínimos de P , es decir, x ∈ 2 | n | tal que 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)$pero , ¬ P ( y ) . Desde el ancho de 2 | n | es ($\forall y \subset x$$\neg P(y)$$2^{|n|}$, podría haber exponencialmente muchos elementos mínimos y, por lo tanto, el tiempo de ejecución de dicho algoritmo podría ser exponencial en general. Sin embargo, ¿podría existir un algoritmo para esta tarea que sea polinómico en el tamaño de la salida?$n \choose n/2$

[Contexto: Una pregunta más general se le pidió , pero no había ningún intento en las respuestas para evaluar la complejidad del algoritmo en el tamaño de la salida. Si supongo que solo hay un elemento mínimo, por ejemplo, entonces puedo realizar una búsqueda binaria después de esta respuesta y encontrarlo. Sin embargo, si deseo seguir encontrando elementos más mínimos, necesito mantener la información actual que tengo sobre de manera que sea manejable continuar la búsqueda sin perder tiempo en lo que ya se conoce. ¿Es posible hacer esto y encontrar todos los elementos mínimos en tiempo polinómico en el tamaño de la salida?]$P$

Idealmente, me gustaría entender si esto se puede hacer con DAG generales, pero ya no sé cómo responder la pregunta para .$2^{|n|}$

Su problema se conoce en la literatura de aprendizaje como "aprender funciones monótonas utilizando consultas de membresía". Una clase de funciones monótonas para las que se pueden identificar todos los términos mínimos se conoce como "polinomialmente aprendible usando consultas de membresía".

$t$$n$$t$