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 n \ choisissez 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 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 .
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
la source