Bueno eso depende. Si hace un reclamo real de tener una solución de tiempo polinómico para un lenguaje que es NP-hard, es probable que la academia considere su declaración en la misma línea como una prueba de 1 = 2. Las personas que han analizado este problema con seriedad dentro de la academia estarán bastante incrédulas ante tal afirmación.
Dicho esto, hay problemas NP-hard que permiten heurísticas razonables para resolver el problema, y para ciertos subconjuntos de problemas NP-hard, estas heurísticas pueden ser muy efectivas. Encontrar heurísticas únicas que se completen dentro del tiempo polinómico puede ser valioso. Esto es particularmente cierto dentro de la investigación de operaciones donde, a pesar de que hay muchos problemas que son NP-hard, todavía puede haber heurísticas efectivas.
Del mismo modo, encontrar nuevas soluciones “aproximadas” puede ser útil. Por ejemplo, el problema de optimización del vendedor ambulante es NP-hard, pero en la práctica puede obtener una solución “suficientemente buena” utilizando la heurística.
- ¿Qué algoritmo debo usar para crear un solucionador de Sudoku?
- ¿Es posible para mí ser un programador exitoso si odio las matemáticas?
- ¿Cómo se relacionan los cierres del lenguaje de programación con el cierre en matemáticas?
- ¿Podría alguien explicarme en términos simples el significado de la teoría de la complejidad, la teoría del caos y la teoría de juegos?
- Cómo hacer una forma generalizada a partir de un conjunto dado de expresiones (pasos / algoritmo de deseo)
Finalmente, si eres estudiante, siempre vale la pena explorar este espacio tú mismo. Tiene sentido, por ejemplo, buscar soluciones efectivas para problemas NP-difíciles hasta el momento en que pueda construir una intuición sobre lo que se necesitaría para resolverlos. Como académico, este es un ejercicio fructífero solo en términos de su propia educación. Sin embargo, no debe entrar con grandes esperanzas de encontrar nuevos resultados. Algunos desalentarían el intento de comenzar incluso como “una pérdida de tiempo”, pero esto ignora la necesidad de comprender el problema.
