problema de la mochila NP-completo
question: ¿Cuál es un ejemplo de un problema al que los algoritmos eficaces han proporcionado una solución a pesar de la intratabilidad asociada con la amplitud de tamaños?, context: Lo que la intratabilidad significa en la práctica es un debate abierto. Decir que un problema no está en P no implica que todos los casos grandes del problema sean difíciles o incluso que la mayoría de ellos lo son. Por ejemplo, el problema de decisión en la aritmética de Presburger se ha demostrado que no está en P, sin embargo, se han escrito algoritmos que resuelven el problema en tiempos razonables en la mayoría de los casos. Del mismo modo, los algoritmos pueden resolver el problema de la mochila NP-completo en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo.
¿Cuál es un ejemplo de un problema al que los algoritmos eficaces han proporcionado una solución a pesar de la intratabilidad asociada con la amplitud de tamaños?
el problema de la mochila NP-completo en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo.
Lo que la intratabilidad significa en la práctica es un debate abierto. Decir que un problema no está en P no implica que todos los casos grandes del problema sean difíciles o incluso que la mayoría de ellos lo son. Por ejemplo, el problema de decisión en la aritmética de Presburger se ha demostrado que no está en P, sin embargo, se han escrito algoritmos que resuelven el problema en tiempos razonables en la mayoría de los casos. Del mismo modo, los algoritmos pueden resolver el problema de la mochila NP-completo en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo.
el <hl> problema de la mochila NP-completo <hl> en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo.
Lo que la intratabilidad significa en la práctica es un debate abierto. Decir que un problema no está en P no implica que todos los casos grandes del problema sean difíciles o incluso que la mayoría de ellos lo son. Por ejemplo, el problema de decisión en la aritmética de Presburger se ha demostrado que no está en P, sin embargo, se han escrito algoritmos que resuelven el problema en tiempos razonables en la mayoría de los casos. Del mismo modo, los algoritmos pueden resolver el <hl> problema de la mochila NP-completo <hl> en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo.
Lo que la intratabilidad significa en la práctica es un debate abierto. Decir que un problema no está en P no implica que todos los casos grandes del problema sean difíciles o incluso que la mayoría de ellos lo son. Por ejemplo, el problema de decisión en la aritmética de Presburger se ha demostrado que no está en P, sin embargo, se han escrito algoritmos que resuelven el problema en tiempos razonables en la mayoría de los casos. Del mismo modo, los algoritmos pueden resolver <hl> el problema de la mochila NP-completo en una amplia gama de tamaños en menos de tiempo cuadrático y los solucionadores SAT manejan rutinariamente grandes instancias del problema de satisfacibilidad booleana NP-completo. <hl>