Éléments minimaux d'un prédicat monotone sur l'ensemble de puissance

Considérons un prédicat monotone sur l'ensemble de puissance (ordonné par inclusion). Par "monotone" je veux dire: tel que , si puis . Je cherche un algorithme pour trouver tous les éléments minimaux de , c'est-à-dire les tels que mais , . Puisque la largeur de est $P$ $2^{|n|}$ $\forall x, y \in 2^{|n|}$ $x \subset y$ $P(x)$ $P(y)$ $P$ $x \in 2^{|n|}$ $P(x)$ $\forall y \subset x$ $\neg P(y)$ $2^{|n|}$ $n \choose n/2$ , il pourrait y avoir de manière exponentielle de nombreux éléments minimaux, et donc le temps d'exécution d'un tel algorithme pourrait être exponentiel en général. Cependant, pourrait-il exister un algorithme pour cette tâche qui soit polynomial dans la taille de la sortie?

[Contexte: Une question plus générale a été posée mais il n'y a eu aucune tentative dans les réponses pour évaluer la complexité de l'algorithme dans la taille de la sortie. Si je suppose qu'il n'y a qu'un seul élément minimal, par exemple, alors je peux effectuer une recherche binaire après cette réponse et la trouver. Cependant, si je veux continuer à trouver des éléments plus minimes, je dois maintenir les informations actuelles que j'ai sur $P$ d'une manière qui rendrait plus facile de poursuivre la recherche sans perdre de temps sur ce qui est déjà connu. Est-il possible de faire cela et de trouver tous les éléments minimaux en temps polynomial dans la taille de la sortie?]

Idéalement, j'aimerais comprendre si cela peut être fait avec des DAG généraux, mais je ne sais déjà pas comment répondre à la question pour $2^{|n|}$ .

ds.algorithms ds.data-structures partial-order order-theory search-problem a3nm
la source

Le jeu de puissance ordonné par inclusion est un DAG (avec les différentes parties de comme sommets et une arête entre les couples de parties qui sont incluses les unes dans les autres, en ne gardant que la réduction transitive de ce graphique pour supprimer les bords redondants impliqués par la transitivité). Il semble naturel de poser la même question sur les DAG arbitraires.

2^{| n |}

$2^{|n|}$

{1, . . ., n}

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

a3nm

Réponses:

Votre problème est connu dans la littérature d'apprentissage comme «l'apprentissage des fonctions monotones à l'aide de requêtes d'appartenance». Une classe de fonctions monotones pour lesquelles on peut identifier tous les termes est connue comme "apprenant polynomialement en utilisant des requêtes d'appartenance".

Il semble que l'existence d'un algorithme de temps polynomial soit toujours ouverte. Schmulevich et al. prouver que "Presque toutes les fonctions booléennes monotones sont polynomialement apprenables en utilisant des requêtes d'appartenance". Si nous exigeons également que le ème minterm soit généré dans le polynôme temporel en et , alors le problème est équivalent à la dualisation monotone, comme l'ont montré Bioch et Ibaraki . Voici une enquête sur la dualisation monotone. $t$ $n$ $t$

Yuval Filmus
la source

Merci pour cette réponse extrêmement utile. Connaissez-vous des généralisations à des DAG arbitraires (c'est-à-dire plus que les cas spéciaux de la section 5.2 d'Eiter et al.)?

a3nm

Non, malheureusement non.

Yuval Filmus

OK, je vais accepter cette réponse de toute façon. Remarques supplémentaires: (1) cette réponse concerne la complexité de calcul, pas la complexité du nombre d'évaluations de (voir cstheory.stackexchange.com/a/14862/4795 pour ce dernier cas), et (2) l'ouverture exacte la question est "pouvez-vous apprendre une fonction booléenne monotone en temps polynomial en et son nombre de minima et maxima", il n'y a aucun espoir de le faire en temps polynomial en et le nombre de maxima car il peut y avoir un nombre linéaire de maxima mais un nombre exponentiel de minima (cf. sec 6.1 paragraphe 2 de l'enquête mentionnée ci-dessus).

P

$P$

n

$n$

n

$n$

a3nm

Voir mon autre question cstheory.stackexchange.com/q/16258/4795 pour plus d'informations sur la complexité de requête globale la plus défavorable pour les DAG arbitraires.

a3nm

re dualisation monotone (CNF ← → DNF) & DAG. ressemble beaucoup à un théorème du livre juknas complexité de la fonction booléenne sec 9.4. "critère des limites inférieures" thm 9.17

vzn