mercredi 14 mai 2008

La complexité de l'enseignement

Concernant le problème TEACH défini ci-dessous, j'ai obtenu un résultat intéressant de complexité.

Problème :
TEACH
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