"Reducibilidad entre problemas combinatorios"
question: ¿Cuál es el artículo escrito por Richard Karp en 1972 que marcó el comienzo de una nueva era de entendimiento entre la intratabilidad y los problemas NP-completos?, context: En 1967, Manuel Blum desarrolló una teoría de la complejidad axiomática basada en sus axiomas y demostró ser un resultado importante, el llamado teorema de aceleración. El campo realmente comenzó a florecer en 1971 cuando el investigador estadounidense Stephen Cook y, trabajando de forma independiente, Leonid Levin en la URSS, demostraron que existen problemas prácticamente relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, "Reducibilidad entre problemas combinatorios", en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad.
¿Cuál es el artículo escrito por Richard Karp en 1972 que marcó el comienzo de una nueva era de entendimiento entre la intratabilidad y los problemas NP-completos?
En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, "Reducibilidad entre problemas combinatorios" , en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad.
En 1967, Manuel Blum desarrolló una teoría de la complejidad axiomática basada en sus axiomas y demostró ser un resultado importante, el llamado teorema de aceleración. El campo realmente comenzó a florecer en 1971 cuando el investigador estadounidense Stephen Cook y, trabajando de forma independiente, Leonid Levin en la URSS, demostraron que existen problemas prácticamente relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, "Reducibilidad entre problemas combinatorios", en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad.
En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, <hl> "Reducibilidad entre problemas combinatorios" <hl> , en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad.
En 1967, Manuel Blum desarrolló una teoría de la complejidad axiomática basada en sus axiomas y demostró ser un resultado importante, el llamado teorema de aceleración. El campo realmente comenzó a florecer en 1971 cuando el investigador estadounidense Stephen Cook y, trabajando de forma independiente, Leonid Levin en la URSS, demostraron que existen problemas prácticamente relevantes que son NP-completos. En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, <hl> "Reducibilidad entre problemas combinatorios" <hl>, en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad.
En 1967, Manuel Blum desarrolló una teoría de la complejidad axiomática basada en sus axiomas y demostró ser un resultado importante, el llamado teorema de aceleración. El campo realmente comenzó a florecer en 1971 cuando el investigador estadounidense Stephen Cook y, trabajando de forma independiente, Leonid Levin en la URSS, demostraron que existen problemas prácticamente relevantes que son NP-completos. <hl> En 1972, Richard Karp llevó esta idea un salto hacia adelante con su artículo histórico, "Reducibilidad entre problemas combinatorios" , en el que mostró que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad. <hl>