21
question: ¿Cuántos problemas teóricos combinatorios y de grafos, que antes se creía estaban plagados de intratabilidad, hicieron la dirección de papel de Karp?, 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ántos problemas teóricos combinatorios y de grafos, que antes se creía estaban plagados de intratabilidad, hicieron la dirección de papel de Karp?
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.
que <hl> 21 <hl> 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 <hl> 21 <hl> 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ó <hl> que 21 problemas teóricos combinatorios y de grafos, cada uno infame por su computabilidad. <hl>