Según tengo entendido, está haciendo dos preguntas: (1) existen, por ejemplo, algoritmos SAT que son más inteligentes que la fuerza bruta ingenua, y (2) existen algoritmos que simplemente dan una respuesta SÍ / NO al resolver un problema NP-completo sin encontrar realmente la solución. Contestaré ambas preguntas en este orden.
(1) Es perfectamente posible resolver un problema sin fuerza bruta, es decir, sin tratar ingenuamente todas las posibilidades. Para tomar su ejemplo, los solucionadores de SAT completos modernos pueden aplicar algoritmos inteligentes que infieren o prueban ciertas asignaciones (parciales) que no pueden conducir a una solución, por lo que ni siquiera examinan esa parte.
En términos más generales, incluso los problemas NP-duros a menudo exhiben algún tipo de punto de apoyo algorítmico que nos permite diseñar un algoritmo más rápido que la fuerza bruta. El campo de esta investigación son los algoritmos exactos (exponenciales) . Tales algoritmos toman tiempo exponencial, pero aún son más rápidos que los algoritmos ingenuos. Por ejemplo, puede resolver TSP en aproximadamentetiempo, donde es el número de ciudades para visitar. Este método no escalará incluso a valores moderados de , pero existe un algoritmo de tiempo clásico de programación dinámica debido a Held & Karp . Para técnicas generales, ver, por ejemplo, ramificación y encuadernación .n!nnO(2nn2)
(2) Existen "algoritmos oracle" para problemas NP-completos que solo generan SÍ / NO sin certificado explícito. Por ejemplo, considere el problema -path:k
(El problema de ruta)k Dado un gráfico y un entero , ¿hay una ruta simple en sobre vértices?GkGk
El problema anterior se ve fácilmente como NP-completo. Un algoritmo para el problema se da en [1]. El algoritmo en sí solo da una respuesta SÍ / NO al problema, pero podemos usar trucos adicionales para construir el -path real . En términos más generales, cuando se le da un "algoritmo oráculo" de este tipo, se pueden usar herramientas de pruebas de grupo combinatorias para extraer el testigo en sí.O∗(2k)k
[1] Williams, Ryan. "Encontrar caminos de longitud en tiempo". Cartas de procesamiento de información 109.6 (2009): 315-318. enlace del editor , PDFkO∗(2k)