Concernant le problème TEACH défini ci-dessous, j'ai obtenu un résultat intéressant de complexité.
Exemple : Un groupe d'étudiants E = {e_1, ..., e_n}, un sujet S et un cours C.
Question : Est-ce qu'au moins k étudiants vont passer le cours ?
Le problème est difficile.
Proposition : Le problème TEACH est NP-difficile.
Preuve : La preuve repose sur une réduction à partir du problème de couplage en 3 dimensions (3D-MATCHING). Détails à venir.
Des inspirations transcendantales me font croire que le problème est aussi NP-complet, quoique je n'ai aucune idée de preuve pour appuyer ma conjecture. Toute contribution est la bienvenue.
Conjecture : Le problème TEACH est NP-complet.
Aucun commentaire:
Enregistrer un commentaire