Enseignement NP-complétude - réductions de Turing vs réductions de Karp

Je m'intéresse à la meilleure façon d'enseigner la complétude NP aux majors en informatique. En particulier, devrions-nous l'enseigner en utilisant des réductions Karp ou en utilisant des réductions Turing?

Je pense que les concepts de complétude et de réduction de NP sont quelque chose que chaque étudiant en informatique devrait apprendre. Cependant, lorsque j'enseigne l'exhaustivité de NP, j'ai remarqué que l'utilisation des réductions de Karp a des inconvénients.

Tout d'abord, les réductions de Karp semblent être inutilement déroutantes pour certains étudiants. La notion intuitive d'une réduction est «si j'ai un algorithme pour résoudre le problème X, je peux aussi l'utiliser pour résoudre le problème Y». C'est très intuitif - mais cela correspond beaucoup mieux aux réductions de Turing qu'aux réductions de Karp. En conséquence, je vois des étudiants qui tentent de prouver l'exhaustivité de NP se laisser égarer par leur intuition et former une preuve incorrecte. Essayer d'enseigner les deux types de réductions et mettre l'accent sur cet aspect des réductions Karp ressemble parfois un peu à un formalisme inutile et prend du temps de classe inutile et l'attention des étudiants sur ce qui ressemble à un détail technique inessentiel; il n'est pas évident pourquoi nous utilisons cette notion plus restreinte de réduction.

Je comprends la différence entre les réductions de Karp et les réductions de Turing (Cook), et comment elles conduisent à différentes notions de complétude NP. Je me rends compte que les réductions de Karp nous donnent une granularité plus fine des distinctions entre les classes de complexité. Ainsi, pour une étude sérieuse de la théorie de la complexité, les réductions de Karp sont évidemment le bon outil. Mais pour les étudiants en informatique qui ne font qu'apprendre cela et ne vont jamais entrer dans la théorie de la complexité, je ne suis pas certain que cette distinction plus fine soit critique soit critique pour eux.

Enfin, en tant qu'étudiant, je me souviens m'être senti perplexe lorsque j'ai rencontré un problème comme la "tautologie" - par exemple, étant donné une formule booléenne, vérifiez s'il s'agit d'une tautologie. Ce qui était déroutant, c'est que ce problème est clairement difficile: tout algorithme polynomial pour le temps impliquerait que $P=NP$; et résoudre ce problème est évidemment aussi difficile que de résoudre le problème de la tautologie. Cependant, même si intuitivement la tautologie est aussi difficile que la satisfiabilité, la tautologie n'est pas NP-difficile. Oui, je comprends aujourd'hui pourquoi c'est le cas, mais à l'époque je me souviens avoir été perplexe. (Ce qui m'est venu à l'esprit une fois que j'ai finalement compris était: pourquoi faisons-nous cette distinction entre NP-dur et co-NP-dur, de toute façon? Cela semble artificiel et peu motivé par la pratique. Pourquoi nous concentrons-nous plutôt sur le NP que la co-NP? Ils semblent tout aussi naturels. D'un point de vue pratique, la co-NP-dureté semble avoir essentiellement les mêmes conséquences pratiques que la NP-dureté, alors pourquoi sommes-nous tous accrochés à cette distinction? Oui, je connais la réponses, mais en tant qu'étudiant, je me souviens que cela rendait le sujet plus obscur et moins motivé.)

Voici donc ma question. Lorsque nous enseignons la complétude NP aux étudiants, est-il préférable d'enseigner en utilisant des réductions de Karp ou des réductions de Turing? Quelqu'un a-t-il essayé d'enseigner le concept de complétude NP en utilisant des réductions de Turing? Si oui, comment est-il allé? Y aurait-il des pièges ou des inconvénients non évidents si nous enseignions les concepts en utilisant les réductions de Turing et si nous sautions les problèmes conceptuels associés aux réductions de Karp?

En relation: voir ici et ici , qui mentionne que la raison pour laquelle nous utilisons des réductions de Karp dans la littérature est parce qu'elle nous permet de distinguer entre la dureté NP et la dureté co-NP. Cependant, il ne semble pas donner de réponse centrée sur une perspective pédagogique de savoir si cette capacité est critique pour les objectifs d'apprentissage d'une classe d'algorithmes qui devraient être suivis par chaque CS majeur. Voir également ici sur cstheory.SE , qui a une discussion similaire.

Je dirais très certainement enseigner l'utilisation des réductions de Karp (plusieurs). Indépendamment des avantages de l'utilisation des réductions de Turing poly-temps (Cook), les réductions Karp sont le modèle standard.

Tout le monde utilise Karp et le principal écueil de l'enseignement de Cook est que vous vous retrouverez avec toute une classe d'étudiants qui deviennent pathologiquement confus lorsqu'ils lisent un manuel ou essaient de discuter du sujet avec quelqu'un qui n'a pas été enseigné par vous.

Je suis d'accord que les réductions Cook sont de plusieurs manières plus sensées et qu'il n'y a pas de distinction entre la dureté NP et la dureté coNP en termes pratiques, dans le sens où elles signifient toutes les deux "Ce problème est assez difficile et vous n'obtiendrez pas algorithme général, efficace et exact qui peut faire face à de grandes instances. " D'un autre côté, la distinction entre NP et coNP n'est pas entièrement un artefact d'une théorie basée sur les réductions de Karp: vous ne parlez pas souvent de graphiques qui ne sont pas à 3 coloris ou dans lesquels chaque ensemble de  sommets contient à au moins un bord. D'une manière ou d'une autre, la version "naturelle" du problème semble souvent être en NP plutôt qu'en coNP.$k$

Il vaut mieux enseigner les deux ! Un majeur en informatique devrait connaître les deux.

Je ne connais personne qui utilise les réductions Cook pour enseigner l'exhaustivité de NP, les théoriciens de la complexité ne le font évidemment pas, les théoriciens de la non-complexité suivent généralement la définition standard depuis l'article de Karp et sont utilisés dans tous les manuels (à ma connaissance). Cela leur causera beaucoup de confusion plus tard si vous ne suivez pas la terminologie standard.

Les réductions de cuisson résolvent essentiellement les problèmes à l'aide de sous-programmes de boîte noire. Ils sont faciles à expliquer et à motiver si vos élèves ont une certaine expérience en programmation. Ils sont essentiels car sans réductions Cook, vous ne pouvez pas discuter des réductions entre les problèmes de recherche, les problèmes d'optimisation, etc.

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{coNP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}$

$x\in A$$f(x) \in B$

La notion intuitive d'une réduction est «si j'ai un algorithme pour résoudre le problème X, je peux aussi l'utiliser pour résoudre le problème Y».

une façon intéressante d'aborder ce problème pédagogique particulier est de réaliser que l'exhaustivité du NP présente des similitudes et des analogies avec l'indécidabilité qui n'est pas non plus intuitive. les élèves n'entrent en classe qu'après avoir entendu parler d'algorithmes qui s'arrêtent. mais le théorème principal du TCS est qu'il existe des problèmes pour lesquels il n'y a pas de solution garantie, c'est-à-dire le problème d'arrêt. et en fait, les problèmes indécidables peuvent commencer à sembler loin d'être artificiels et sont apparemment quelque peu omniprésents.

ainsi, la théorie nous indique la manière de considérer le calcul fondamentalement comme un processus qui peut renvoyer une réponse dans certaines circonstances. dans d'autres circonstances, ce n'est pas le cas. pour l'exhaustivité et la décidabilité de NP, la question fondamentale et la plus générale est "y a-t-il un algorithme qui retourne Yen temps P". mais cela ne dit rien sur un algorithme qui retourne Nen temps P. un algorithme pourrait retourner Yen P temps pour une instance mais ne pas retourner de réponse sur d'autres instances. la théorie nous dit qu'il y a vraiment une différence distincte à laquelle nous devons prêter une attention particulière. s'il n'est pas intuitif, cela signifie que nos intuitions fondamentales doivent être réajustées (comme c'est souvent le cas dans l'enseignement théorique).