Solución es un término muy general. Si te refieres a un algoritmo de tiempo polinómico determinista , entonces la respuesta es NO . Eso es lo mismo que hacer una pregunta P vs NP.
Pero, ha habido mucho progreso en términos de algoritmos aleatorios y de aproximación . Por ejemplo: SAT (el problema canónico de NP completo) se sabe que posee algoritmo aleatorio de tiempo [matemático] O (4/3) ^ n [/ matemático], que funciona muy bien en la práctica. Del mismo modo, el problema Max-SAT tiene un algoritmo de tiempo polinómico con un factor de aproximación de (7/8). También se sabe que encontrar una solución para Max-SAT con cualquier factor de aproximación (7/8 + [matemática] \ epsilon [/ matemática]) para cualquier [matemática] \ epsilon> 0 [/ matemática] es tan difícil como resolver P vs Problema NP.
Para fines prácticos como en Neurociencia, Física Moderna, etc., hay muchas heurísticas (en lugar de algoritmos) que se usan comúnmente para resolver SAT. Producen la solución razonablemente bien en la práctica.
- ¿Qué software / algoritmo se usa para hacer partidos de la liga de fútbol o cualquier evento deportivo enorme?
- ¿Cómo podemos dividir un conjunto dado de números (posiblemente negativos) en dos partes que tienen el mismo promedio?
- ¿Un montón necesita usar una cola prioritaria?
- ¿Qué libro de algoritmos introductorios debería leer una mente matemáticamente inclinada?
- Cómo ejecutar cruces en algoritmos genéticos con cromosomas codificados por gráficos
Si algunas conjeturas famosas son ciertas (como la hipótesis del tiempo exponencial fuerte), entonces es poco probable que alguna vez podamos resolver problemas de NP completo en tiempo polinómico determinista.
