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.

Pourquoi les nombres entiers sont parfois essentiels ?

On a tendance à sous-estimer l'utilité et la signification des nombres entiers. Dans cet article du Globe and Mail du 10 mai, on peut lire cette charmante phrase :

Nearly 800 superdelegates will attend the convention. Mr. Obama has endorsements from 275, according to the latest tally by The Associated Press. Ms. Clinton has 271.5.

Hum, j'ignore ce qu'est un demi-superdélégué. Pourquoi madame Clinton a-t-elle l'appui de 271.5 superdélégués ? D'où vient ce demi frauduleux ? On s'imagine qu'il s'agit d'une approximation statistique basée sur un modèle quelconque. Mais, dans ce contexte, l'utilisation de résultats fractionnaires n'a aucun sens.

Parfois, on peut interpréter un résultat fractionnaire comme une proportion. Or, ici, il est question d'un nombre de personnes, pas d'une proportion. Il est donc tout à fait déraisonnable de dire que madame Clinton a l'appui d'un demi-délégué.