Enseñanza de la completitud NP: reducciones de Turing vs reducciones de Karp

Me interesa la cuestión de cómo enseñar mejor la completitud de NP a los estudiantes de informática. En particular, ¿deberíamos enseñarlo usando reducciones de Karp o reducciones de Turing?

Siento que los conceptos de NP-completitud y reducciones son algo que todo experto en informática debería aprender. Sin embargo, al enseñar la completitud de NP, he notado que el uso de las reducciones de Karp tiene algunas desventajas.

En primer lugar, las reducciones de Karp parecen ser innecesariamente confusas para algunos estudiantes. La noción intuitiva de una reducción es "si tengo un algoritmo para resolver el problema X, entonces también puedo usarlo para resolver el problema Y". Eso es muy intuitivo, pero se asigna mucho mejor a las reducciones de Turing que a las reducciones de Karp. Como resultado, veo que los estudiantes que están tratando de demostrar la integridad de NP se desvían por su intuición y forman una prueba incorrecta. Tratar de enseñar ambos tipos de reducciones y enfatizar este aspecto de las reducciones de Karp a veces se siente un poco como un formalismo innecesario y ocupa tiempo innecesario en la clase y la atención de los estudiantes en lo que se siente como un detalle técnico no esencial; no es evidente por qué usamos esta noción más restringida de reducción.

Entiendo la diferencia entre las reducciones de Karp y las reducciones de Turing (Cook), y cómo conducen a diferentes nociones de integridad de NP. Me doy cuenta de que las reducciones de Karp nos dan una granularidad más fina de distinciones entre clases de complejidad. Entonces, para un estudio serio de la teoría de la complejidad, las reducciones de Karp son obviamente la herramienta correcta. Pero para los estudiantes de ciencias de la computación que simplemente están aprendiendo esto y nunca van a entrar en la teoría de la complejidad, no estoy seguro de si esta distinción más precisa es crítica para ellos.

Finalmente, como estudiante, recuerdo que me sentí perplejo cuando me encontré con un problema como "tautología", por ejemplo, dada una fórmula booleana, verifique si es una tautología. Lo que era confuso era que este problema es claramente difícil: cualquier algoritmo de tiempo polinómico implicaría que $P=NP$; y resolver este problema es obviamente tan difícil como resolver el problema de la tautología. Sin embargo, aunque intuitivamente la tautología es tan difícil como la satisfacción, la tautología no es NP-difícil. Sí, entiendo hoy por qué este es el caso, pero en ese momento recuerdo estar perplejo por esto. (Lo que me pasó por la cabeza una vez que finalmente entendí fue: ¿Por qué, de todos modos, hacemos esta distinción entre NP-hard y co-NP-hard? Eso parece artificial y no está muy bien motivado por la práctica. ¿Por qué nos centramos más bien en NP? que la co-NP? Parecen igualmente naturales. Desde una perspectiva práctica, la dureza co-NP parece tener esencialmente las mismas consecuencias prácticas que la dureza NP, entonces, ¿por qué nos obsesionamos con esta distinción? Sí, sé que respuestas, pero como estudiante, recuerdo que esto hizo que el tema se sintiera más arcano y mal motivado).

Así que mi pregunta es esta. Cuando enseñamos la completitud NP a los estudiantes, ¿es mejor enseñar usando reducciones de Karp o reducciones de Turing? ¿Alguien ha intentado enseñar el concepto de integridad de NP utilizando reducciones de Turing? Si es así, como fue? ¿Habría dificultades o desventajas no obvias si enseñáramos los conceptos usando las reducciones de Turing y omitiéramos los problemas conceptuales asociados con las reducciones de Karp?

Relacionado: vea aquí y aquí , que menciona que la razón por la que usamos las reducciones de Karp en la literatura es porque nos permite distinguir entre la dureza NP y la dureza co-NP. Sin embargo, no parece dar ninguna respuesta que se centre en una perspectiva pedagógica de si esta capacidad es crítica para los objetivos de aprendizaje de una clase de algoritmos que debe tomar cada estudiante de CS. Ver también aquí en cstheory.SE , que tiene una discusión similar.

Definitivamente diría que enseñe usando reducciones de Karp (muchos-uno). Independientemente de los beneficios de utilizar reducciones de Turing de poli-tiempo (Cook), las reducciones de Karp son el modelo estándar.

Todo el mundo usa Karp y el principal obstáculo de la enseñanza de Cook es que terminarás con una clase completa de estudiantes que se confunden patológicamente cada vez que leen un libro de texto o tratan de discutir el tema con alguien a quien no se te enseñó.

Estoy de acuerdo en que las reducciones de Cook son más sensibles en varios aspectos y que no hay distinción entre la dureza NP y la dureza coNP en términos prácticos, en el sentido de que ambas significan "Este problema es bastante difícil y no se obtendrá algoritmo general, eficiente y exacto que puede hacer frente a grandes instancias ". Por otro lado, la distinción entre NP y coNP no es enteramente un artefacto de una teoría basada en las reducciones de Karp: a menudo no se habla de gráficos que no sean de 3 colores o en los que cada conjunto de  vértices contenga Al menos un borde. De alguna manera, la versión "natural" del problema a menudo parece estar en NP en lugar de coNP.$k$

¡Es mejor enseñar ambos ! Un experto en informática debe saber sobre ambos.

No conozco a nadie que use las reducciones de Cook para enseñar la integridad de NP, los teóricos de la complejidad obviamente no lo hacen, los teóricos de la no complejidad suelen seguir la definición estándar desde el artículo de Karp y se usa en todos los libros de texto (que yo sepa). Les causará mucha confusión más adelante si no siguen la terminología estándar.

Las reducciones de cocción esencialmente resuelven problemas usando subrutinas de recuadro negro. Son fáciles de explicar y motivar si sus estudiantes tienen experiencia en programación. Son esenciales ya que sin las reducciones de Cook no se pueden discutir las reducciones entre problemas de búsqueda, problemas de optimización, 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 noción intuitiva de una reducción es "si tengo un algoritmo para resolver el problema X, entonces también puedo usarlo para resolver el problema Y".

Una forma interesante de abordar este problema de enseñanza en particular es darse cuenta de que la integridad de NP tiene similitudes y analogías con la indecidibilidad, que tampoco es intuitiva. los estudiantes ingresan a clase solo cuando han escuchado sobre algoritmos que se detienen. pero el teorema principal de TCS es que existen problemas para los cuales no hay una solución garantizada, es decir, el problema de detención. y, de hecho, los problemas indecidibles pueden comenzar a verse lejos de ser artificiales, y aparentemente son algo ubicuos.

entonces, la teoría nos dice la forma de ver la computación fundamentalmente como un proceso que puede devolver una respuesta en algunas circunstancias. en otras circunstancias, puede que no. para la integridad y capacidad de decisión de NP, la pregunta fundamental y más general es "¿existe un algoritmo que regrese Yen el tiempo P". pero esto no dice nada sobre un algoritmo que regresa Nen tiempo P un algoritmo podría regresar Yen tiempo P para una instancia pero no devolver una respuesta en otras instancias. La teoría nos dice que realmente hay una diferencia clara a la que debemos prestar mucha atención. si no es intuitivo, significa que nuestras intuiciones fundamentales deben reajustarse (como suele ser el caso en la enseñanza teórica).