No estoy de acuerdo con la premisa de la pregunta. Hay algunos problemas NP-hard que no tienen soluciones, pero como explicaré, hay áreas enteras de algoritmos dedicados a tratar el escenario en el que es posible que nunca encontremos algoritmos exactos eficientes para problemas NP-hard. Un ejemplo de un problema que técnicamente es NP-hard que no tiene solución es el Problema de detención, pero esto se debe a que NP-hard implica todos los problemas, al menos, tanto como los problemas más difíciles de la clase de complejidad NP. Los problemas (a menos que pueda demostrar que tienen una relación) se deben considerar caso por caso. Un enfoque que puede ayudar a resolver un problema puede fallar miserablemente por otro problema.
Mencionaré brevemente 2 enfoques (de los cuales soy un gran admirador) que surgieron de la cuestión de querer enfoques matemáticamente rigurosos para lidiar con problemas difíciles de NP, pero aún se puede obtener el deseo de soluciones eficientes :
- Algoritmos de aproximación ( Algoritmo de aproximación – Wikipedia): en lugar de tratar de encontrar la solución óptima exacta, encuentre una solución que esté dentro de un factor óptimo. Aquí sacrificamos la calidad de la solución por un algoritmo eficiente. Tenga en cuenta que si bien esto parece que condenaría gran parte de la calidad, créalo o no, hay muchos problemas de optimización NP-hard que se pueden aproximar muy estrechamente al verdadero óptimo aún en el tiempo polinómico. No debe confundirse con una heurística más amplia, estas garantías (cuán cercanas son las soluciones producidas al óptimo) están demostradas matemáticamente y no son cosas manuales.
- Algoritmos parametrizados (Complejidad parametrizada – Wikipedia): la idea es parametrizar los problemas en términos que algunos llaman parámetro , luego puede ver este parámetro como otra parte de la entrada. Por ejemplo, el problema clásico de NP-hard Vertex Cover en realidad se puede resolver de manera bastante eficiente si se supone que el tamaño de la cubierta de vértice es el parámetro. Se sabe que problemas como Vertex Cover son manejables con parámetros fijos (FPT) . Es decir, si arregla el parámetro, el problema se vuelve eficiente de resolver. Las personas que estudian esta área a menudo intentan identificar parámetros clave que permiten la existencia de algoritmos eficientes (y diseñan algoritmos eficientes que utilizan estos parámetros), esto muchas veces permite que surja una perspectiva muy diferente que no podría encontrarse por otros medios. También hay otra jerarquía de complejidad asociada con problemas parametrizados llamada la Jerarquía W (ver Complejidad parametrizada – Wikipedia).
En otra nota, es importante cuantificar lo que realmente significa “sin soluciones”. Cuando un informático escucha “no hay soluciones”, significa que el problema es indecidible típicamente, no es que sea intratable (a menos que proporcione más contexto). Por ejemplo, existen soluciones para muchos problemas NP-hard, solo que son algoritmos de tiempo exponencial.
- ¿Cuál es una buena idea de aprendizaje automático simple pero pasada por alto para LinkedIn?
- ¿Cómo difiere el proceso de solicitud para los Premios de Investigación de Google del proceso de solicitud de subvención académica estándar?
- ¿Cómo se supera la intimidación del conocimiento técnico?
- ¿Qué tan importante es la interpretabilidad para un modelo en Machine Learning?
- ¿Cómo es el trabajo en Broadcom, Hyderabad?
